百度2016年暑期实习生笔试题 —— 单词接龙
拉姆刚开始学习英文单词，对单词排序很感兴趣。如果给拉姆一组单词，他能够迅速确定是否可以将这些单词排列在一个列表中，使得该列表中任何单词的首字母与前一单词的尾字母相同。你能编写一个程序来帮助拉姆进行判断吗？
输入描述：
输入包含多组测试数据。对于每组测试数据，第一行为一个正整数n，代表有n个单词。然后有n个字符串，代表n个单词。保证：2<=n<=200，每个单词长度大于1且小于等于10，且所有单词都是由小写字母组成。
输出描述：
对于每组数据，输出"Yes"或"No"
输入例子1:
3
abc
cdefg
ghijkl
输出例子1：
Yes
输入例子2：
4
abc
cdef
fghijk
xyz
输出例子2：
No
由题意可知，对于输入单词的顺序我们是可以调整的，也就是说无论怎么调整单词的顺序，只要能形成接龙即可。
可能有人会想到通过调整单词的顺序，比如按首字母或尾字母对输入的单词进行重新排序再依次检查首尾是否可以形成接龙，这样就掉入了本题的第一个陷阱。事实上，在本题中26个英文字母是没有所谓的先后顺序的，因为我们要判断的是这些单词能否形成一条接龙，即使你的首字母是a而我的首字母是z，但是你的单词是abc中而我的是单词zxa，你的单词仍然排在我的后面。
这里有人可能已经看出来了，如果把每个单词看成一条有向边，首尾字母看成边上的起点和终点，问题就转化成了判断一个有向图是否可以表示为一条（不闭合的）欧拉路径或欧拉回路的一笔画问题。
根据有向图中欧拉路径的判定定理
一个连通的有向图可以表示为一条从起点到终点的（不闭合的）欧拉路径的充要条件是： 起点的出度比入度多1， 终点的入度比出度多1，而其它顶点的入度和出度都相等。
一个连通的有向图可以表示为一条欧拉回路的充要条件是：每个顶点的入度和出度都相等
注意到上面我对连通的三个字进行了加粗，目的是强调不要忘记判断有向图的连通性（这里只要满足弱连通即可），对于百度那道笔试题网上很多人只考虑到统计点的入度与出度来判断是否能形成接龙，而没有检验有向图的连通性，虽然这样的代码能通过牛客OJ上所有的测试用例，但实际上对于aba，cdc，efe这样的输入却会得到错误的输出"Yes"，原因就是这些单词形成的有向图是不连通的。这也从侧面说明了牛客OJ上用例设计的不够全面。
源码如下：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
while(scan.hasNext())
{
int n = scan.nextInt();
String[] arr = new String[n];
for(int i = 0; i < n ; i++)
arr[i] = scan.next();
System.out.println(WordListOrder.canArrangeWords(n, arr));
}
scan.close();
}
}
class WordListOrder {
public static String canArrangeWords(int n, String[] arr)
{
// 26个英文字母看作26个点,用整数0-25来表示
int[][] directedGraph = new int [26][26];// 邻接矩阵表示有向图
int[] inDegree = new int [26]; // 顶点入度
int[] outDegree = new int [26]; // 顶点出度
boolean[] hasLetter = new boolean[26]; // 标记字母是否出现过
boolean hasEuler = false; // 有狭义欧拉路径或欧拉回路标志
for(int i = 0; i < n; i++)
{
String word = arr[i];
char firstLetter = word.charAt(0);
char lastLetter = word.charAt(word.length()-1);
outDegree[firstLetter - 'a']++;
inDegree[lastLetter - 'a']++;
directedGraph[firstLetter - 'a'][lastLetter - 'a'] = 1; // 有向图
hasLetter[firstLetter - 'a'] = true;
hasLetter[lastLetter - 'a'] = true;
}
int startNum = 0;
int endNum = 0;
for (int vertex = 0; vertex < 26; vertex++)
{
if(outDegree[vertex] - inDegree[vertex] == 1) // 起点
startNum++;
if(inDegree[vertex] - outDegree[vertex] == 1) // 终点
endNum++;
if(Math.abs(inDegree[vertex] - outDegree[vertex]) > 1)
{
hasEuler = false;
break;
}
}
boolean isEulerPath = (startNum == 1 && endNum == 1); // 这里指狭义上的欧拉路径，不包括欧拉回路
boolean isEulerCircuit = (startNum == 0 && endNum == 0);// 欧拉回路
if((!isEulerPath) && (!isEulerCircuit)) // 既不是欧拉路径也不是欧拉回路
hasEuler = false;
// 判断是否弱连通
int vertexNum = 0; // 统计图中点的个数
for(int letter = 0; letter < 26; letter++)
{
if(hasLetter[letter])
vertexNum++;
}
int firstWordFirstLetter = arr[0].charAt(0) - 'a';// 以第一个单词的首字母作为起点进行BFS
hasEuler = hasEuler && isConnected(firstWordFirstLetter, vertexNum, directedGraph);
if(hasEuler)
return "Yes";
else
return "No";
}
// 判断有向图是否弱连通，即转换成无向图判断是否连通
public static boolean isConnected(int start, int vertexNum, int[][] directedGraph)
{
int[][] undirectedGraph = new int[26][26];
for(int i = 0; i < 26; i++) // 把有向图转换成无向图
{
for(int j = 0; j < 26; j++)
{
if(directedGraph[i][j] == 1)
{
undirectedGraph[i][j] = 1;
undirectedGraph[j][i] = 1;
}
}
}
Queue<Integer> queue = new LinkedList<Integer>();
boolean[] passedVertex = new boolean[26];
int passedVertexNum = 0;
queue.offer(start);
// 从起点开始进行BFS，统计遍历到点的个数
while(!queue.isEmpty())
{
int currentVertex = queue.poll();
passedVertex[currentVertex] = true;
passedVertexNum++;
for(int vertex = 0; vertex < 26; vertex++)
{
if(undirectedGraph[currentVertex][vertex] == 1 && passedVertex[vertex] == false)
queue.offer(vertex);
}
}
// 遍历到所有的点，证明无向图是连通的
if(passedVertexNum == vertexNum)
return true;
else
return false;
}
}
