자바 Catenyms 구현 (집합 + dfs + 오로라 리 턴)

Description
A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms: dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog
A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,
aloha.aloha.arachnid.dog.gopher.rat.tiger
Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once. Input
The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself. Output
For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output “***” if there is no solution. Sample Input
2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm Sample Output
aloha.arachnid.dog.gopher.rat.tiger
중국어 설명
유의 어 는 마침표 로 구 분 된 한 쌍 의 단어 로 첫 번 째 단어의 마지막 자 모 는 두 번 째 단어의 마지막 자모 와 같다.예 를 들 어 다음은 분류 이름 입 니 다.
개.두더지
두더지
쥐, 호랑이
아 로 하, 아 로 하
거미 강 동물
복합 어 의 는 세 개 또는 세 개 이상 의 단어 로 구 성 된 서열 로 이 단어 들 은 문장 으로 분리 되 어 서로 인접 한 단어 마다 하나의 의 미 를 형성한다.예컨대
아 로 하.아 로 하.거미 강 동물.개.두더지.호랑이.
소문 자 단 어 를 지정 한 사전 입 니 다. 단 어 를 한 번 만 포함 하 는 복합 catenym 을 찾 을 수 있 습 니 다.
입력
표준 입력 의 첫 줄 은 t, 즉 테스트 용례 의 수량 을 포함한다.각 테스트 용례 는 3 < = n < = 1000 - 사전 의 단어 수로 시작한다.뒤에 n 개의 서로 다른 사전 단어 가 있 습 니 다.모든 단어 자체 가 한 줄 에 1 에서 20 개의 소문 자 사이 의 문자열 이다.
출력
모든 테스트 용례 에 대해 한 줄 을 출력 하고 사전 식 최소 복합 클래스 별명 을 제시 합 니 다. 이 클래스 의 별명 은 모든 사전 단 어 를 한 번 씩 포함 하고 있 습 니 다.해결 방안 이 없 으 면 '* *' 를 출력 합 니 다.

package com.liuzhen.practice;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static int MAX = 30;   //     26 
    @SuppressWarnings("unchecked")
    public static ArrayList[] map = new ArrayList[MAX];
    public static String[] path;
    public static int count;  //  DFS        ，        
    public static int start;
    public static int[] inDegree = new int[MAX];
    public static int[] outDegree = new int[MAX];
    public static ArrayList result = new ArrayList();
    
    class MyComparator implements Comparator {

        public int compare(edge arg0, edge arg1) {
            String A = arg0.word;
            String B = arg1.word;
            int judge = A.compareTo(B);
            if(judge > 0)
                return 1;
            else if(judge < 0)
                return -1;
            return 0;
        }
        
    }
    
    static class edge {
        public int a; //          
        public int b; //          
        public String word;  //    
        public boolean used;     //         
        
        public edge(int a, int b, String word) {
            this.a = a;
            this.b = b;
            this.word = word;
            used = false;
        }
    }
    
    public void init(int k) {
        start = MAX;
        for(int i = 0;i < MAX;i++) {
            map[i] = new ArrayList();
            inDegree[i] = 0;
            outDegree[i] = 0;
        }
        path = new String[k];
        for(int i = 0;i < k;i++)
            path[i] = "";
        count = 0;
    }
    
    public boolean judgeDegree() {
        int in = 0, out = 0;
        for(int i = 1;i < map.length;i++) {  // map[i]          
            if(map[i].size() > 1) 
                Collections.sort(map[i], new MyComparator());
        }
        
        for(int i = 0;i < inDegree.length;i++) {
            if(inDegree[i] == outDegree[i])
                continue;
            else if(inDegree[i] - outDegree[i] == 1)
                in++;
            else if(outDegree[i] - inDegree[i] == 1) {
                out++;
                start = i;   //  ，        ，               
            } else 
                return false;
        }
        if(in == out && (in == 0 || in == 1))
            return true;
        return false;
    }
    
    public void dfs(int begin) {
        for(int i = 0;i < map[begin].size();i++) {
            edge temp = map[begin].get(i);
            if(temp.used == false) {
                temp.used = true;
                path[count++] = temp.word;
                dfs(temp.b);
            }
        }
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t > 0) {
            t--;
            int k = in.nextInt();
            test.init(k);
            for(int i = 0;i < k;i++) {
                String A = in.next();
                int a = A.charAt(0) - 'a';
                int b = A.charAt(A.length() - 1) - 'a';
                start = Math.min(start, Math.min(a, b));
                map[a].add(new edge(a, b, A));
                outDegree[a]++;
                inDegree[b]++;
            }
            StringBuilder temp = new StringBuilder("");
            if(test.judgeDegree()) {  //                   
                test.dfs(start);
                if(count == k) {  //   
                    for(int i = 0;i < k;i++) {
                        temp.append(path[i]);
                        if(i != k - 1)
                            temp.append(".");
                    }
                } else {
                    temp.append("***");
                }
            } else {
                temp.append("***");
            }
            result.add(temp.toString());
        }
        for(int i = 0;i < result.size();i++)
            System.out.println(result.get(i));
    }
}

실행 결과:

6
aloha
arachnid
dog
gopher
rat
tiger
oak
maple
elm
aloha.arachnid.dog.gopher.rat.tiger
***