单词(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;
  }
}