Pku1386 Play on Words

各単語をエッジと考えたグラフでオイラーパスが存在するかどうか調べる．

SPOJの方にも同じ問題がある．こっちはRubyで通したかったのだけど，入力を読んで初めの文字と終わりの文字をとってくるだけでTLEになるので保留．

import java.util.*;
public class Main {
	static boolean isConnect(int adj[][],boolean mustVisit[]){
		boolean visited[] = new boolean[adj.length];
		int start = -1;
		for(int i=0;i<26;i++){
			if(mustVisit[i]){
				start = i;
				break;
			}
		}
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		visited[start] = true;
		while(!q.isEmpty()){
			int cp = q.poll();
			for(int i=0;i<adj.length;i++){
				if(visited[i])continue;
				if(adj[cp][i]>0 || adj[i][cp]>0){
					visited[i] = true;
					q.add(i);
				}
			}
		}
		for(int i=0;i<visited.length;i++){
			if(!visited[i] && mustVisit[i])return false;
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i=0;i<t;i++){
			int n = sc.nextInt();
			boolean mustVisit[] = new boolean[26];
			int adj[][] = new int[26][26];
			int in[] = new int[26];
			int out[] = new int[26];
			for(int j=0;j<n;j++){
				String s = sc.next();
				int f = s.charAt(0)-'a';
				int l = s.charAt(s.length()-1)-'a'; 
				adj[f][l]++;
				in[l]++;
				out[f]++;
				mustVisit[l] = true;
				mustVisit[f] = true;
			}
			if(isConnect(adj, mustVisit)){
				int sum = 0;
				for(int j=0;j<in.length;j++)sum+=Math.abs(in[j]-out[j]);
				if(sum==0 || sum==2){
					System.out.println("Ordering is possible.");
				}else{
					System.out.println("The door cannot be opened.");				
				}				
			}else{
				System.out.println("The door cannot be opened.");				
			}
		}
	}
}