单词(Play On Words)

【分析】

       首先需对欧拉道路有所了解。

       存在欧拉道路的充分条件：      

对于无向图而言，如果一个无向图是连通的，且最多只有两个奇点（顶点的度数为奇数），则一定存在欧拉道路。如果有两个奇点，则必须从其中的一个奇点出发，另一个奇点终止；如果奇点不存在，则可以从任意点出发，最终一定会回到该点（称为欧拉回路）。

对于有向图而言，最多只能有两个点的入度不等于出度，而且必须是其中一个点的出度恰好比入度大1（把它作为起点），另一个的入度比出度大1（把它作为终点）。当然，还有一个前提条件：在忽略边的方向后，图必须是连通的。

       对于该题而言，把字母看作结点，单词看成有向边，则问题有解，当且仅当图中有欧拉路径。有向图存在欧拉道路的条件有两个：底图（忽略边方向后得到的无向图）连通，且度数满足上面讨论过的条件。这里判断图连通的方法采用DFS。

用java语言编写程序，代码如下：

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(new BufferedInputStream(System.in));
		int t = input.nextInt();
		for(int i = 0; i < t; i++) {
			int n = input.nextInt();
			int[][] udg = new int[26][26];//无向图（用于判断图是否连通）
			int[][] dg = new int[26][26];//有向图（判断顶点的度数是否符合欧拉道路的条件）
			boolean[] isVisited = new boolean[26];//标记顶点是否已被访问过
			//这里先赋值为true的原因是为了知道哪些顶点是图中所具有的。录入图的信息中，再将其顶点对应的isVisited值赋值为false
			for(int j = 0; j < 26; j++)
				isVisited[j] = true;
			
			for(int j = 0; j < n; j++) {
				String word = input.next();//边
				int first = word.charAt(0) - 'a';//边的起点
				int last = word.charAt(word.length() - 1) - 'a';//边的终点
				udg[first][last] = udg[last][first] = 1;//无向边
				dg[first][last]++;//有向边（统计边的条数，用于计算各顶点的入度与出度）
				isVisited[first] = isVisited[last] = false;
			}
			
			/*for(int j = 0; j < 26; j++)
				System.out.println((char)('a' + j) + " : " + isVisited[j]);*/
			
			boolean b1 = isConnected(udg, isVisited);//判断图是否具有连通性
			boolean b2 = rightDegree(dg);//判断图中的顶点度数是否符合欧拉道路的充分条件
			//System.out.println(b1 + "...." + b2);
			
			if(b1 && b2)
				System.out.println("Ordering is possible.");
			else
				System.out.println("The door cannot be opened.");
		}
	}
	
	//采用DFS判断图是否具有连通性，如果图具有连通性的话，那么DFS只进行一次，否则DFS会进行多次
	public static boolean isConnected(int[][] udg, boolean[] isVisited) {
		int times = 0;
		for(int i = 0; i < 26; i++) {
			if(!isVisited[i]) {
				//System.out.println((char)('a' + i));
				times++;
				dfs(i, udg, isVisited);
			}
		}
		
		if(times > 1)
			return false;
		return true;
	}
	
	public static void dfs(int u, int[][] udg, boolean[] isVisited) {
		if(u < 0 || u >= 26 || isVisited[u])
			return;
		
		isVisited[u] = true;
		for(int v = 0; v < 26; v++)
			if(!isVisited[v] && udg[u][v] > 0)
				dfs(v, udg, isVisited);
	}
	
	public static boolean rightDegree(int[][] dg) {
		Vertex[] vd = new Vertex[26];
		//统计各顶点的入度与出度
		for(int u = 0; u < 26; u++) {
			for(int v = 0; v < 26; v++) {
				if(dg[u][v] > 0) {
					if(vd[u] == null)
						vd[u] = new Vertex();
					if(vd[v] == null)
						vd[v] = new Vertex();
					
					vd[u].outDegree += dg[u][v];
					vd[v].inDegree += dg[u][v];
				}
			}
		}
		
		/*for(int i = 0; i < 26; i++)
			if(vd[i] != null)
			System.out.println((char)('a' + i) + " : " 
			+ vd[i].outDegree + " " + vd[i].inDegree);*/
		//将出度与入度不同的顶点加入到链表中
		ArrayList<Vertex> vdList = new ArrayList<Vertex>();
		for(int i = 0; i < 26; i++) {
			if(vd[i] != null && (vd[i].inDegree != vd[i].outDegree))
				vdList.add(vd[i]);
		}
		
		if(vdList.size() < 2)
			return true;
		else if(vdList.size() == 2) {
				Vertex v1 = vdList.get(0);
				Vertex v2 = vdList.get(1);
				if(((v1.inDegree - v1.outDegree == 1) && (v2.outDegree - v2.inDegree == 1)) 
						|| ((v1.outDegree - v1.inDegree == 1) && (v2.inDegree - v2.outDegree == 1)))
					return true;
			}
		return false;
	}
	
	static class Vertex {
		int v;
		int outDegree;
		int inDegree;
	}
}