能否成环

Description

Given an array of strings A[ ], determine if the strings can be chained together to form a circle. A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained, it will form a circle. For example, for the array arr[] = {"for", "geek", "rig", "kaf"} the answer will be Yes as the given strings can be chained as "for", "rig", "geek" and "kaf".

给定一个字符串数组A[]，判断这些字符串是否可以链接在一起形成一个圆。如果X的最后一个字符与Y的第一个字符相同，则可以将一个字符串X与另一个字符串Y链接在一起。例如，对于数组arr[] = {" for "， "geek"， "rig"， "kaf"}，答案将是Yes，因为给定的字符串可以被链接为"for"， "rig"， "geek"和"kaf"

Input

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow.
The first line of each test case contains a positive integer N, denoting the size of the array.
The second line of each test case contains a N space seprated strings, denoting the elements of the array A[ ].
1 <= T
0 < N
0 < A[i]

输入的第一行包含一个整数T，表示测试用例的数量。然后是测试用例。
每个测试用例的第一行包含一个正整数N，表示数组的大小。
每个测试用例的第二行包含一个N个分隔的字符串，表示数组A[]的元素。

Output

If chain can be formed, then print 1, else print 0.

如果可以形成环，则打印1，否则打印0。

Sample Input

2
3
abc bcd cdf
4
ab bc cd da

Sample Output

0
1

Solution

图是否可以具有遍历所有顶点的循环：
1.对于同一顶点，出度=入度
2.强连接。即对每个顶点使用深度优先遍历，遍历完后图中所有顶点都应该被访问

public class Chain {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int caseNum = in.nextInt();
        for(int i = 0; i < caseNum; i++){
            int len = in.nextInt();
            List<String> strList = new ArrayList<>();
            for(int j = 0; j < len; j++){
                strList.add(in.next());
            }
            if(isChain(strList)){
                System.out.println(1);
            }
            else{
                System.out.println(0);
            }
        }
    }

    public static boolean isChain(List<String> stringList){
        boolean[][] hasEdge = new boolean[26][26];
        boolean[] isVertax = new boolean[26];
        int[] in = new int[26];
        int[] out = new int[26];

        for(int i = 0; i < stringList.size(); i++){
            String str = stringList.get(i);
            int first = str.charAt(0) - 'a';
            int last = str.charAt(str.length() - 1) - 'a';
            isVertax[first] = true;
            isVertax[last] = true;
            out[first]++;
            in[last]++;
            hasEdge[first][last] = true;
        }

        for(int i = 0; i < 26; i++){
            if(in[i] != out[i]){
                return false;
            }
        }

        int start = stringList.get(0).charAt(0) - 'a';
        return isStronglyConnected(hasEdge, isVertax, start);
    }

    public static boolean isStronglyConnected(boolean[][] hasEdge, boolean[] isVertax, int start){
        boolean[] isVisited = new boolean[26];
        dfs(hasEdge, start, isVisited);
        for(int i = 0; i < 26; i++){
            if(isVertax[i] && !isVisited[i]){
                return false;
            }
        }
        return true;
    }

    public static void dfs(boolean[][] hasEdge, int start, boolean[] isVisited){
        isVisited[start] = true;
        for(int i = 0; i < 26; i++){
            if(hasEdge[start][i]){
                if(!isVisited[i]){
                    dfs(hasEdge, i, isVisited);
                }
            }
        }
    }