HDU 2094 產生冠軍

產生冠軍 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6631 Accepted Submission(s): 3163     Problem Description 有一群人，打乒乓球比賽，兩兩捉對撕殺，每兩個人之間最多打一場比賽。 球賽的規則如下： 如果A打敗了B，B又打敗了C，而A與C之間沒有進行過比賽，那麼就認定，A一定能打敗C。 如果A打敗了B，B又打敗了C，而且，C又打敗了A，那麼A、B、C三者都不可能成為冠軍。 根據這個規則，無需循環較量，或許就能確定冠軍。你的任務就是面對一群比賽選手，在經過了若干場撕殺之後，確定是否已經實際上產生了冠軍。   Input 輸入含有一些選手群，每群選手都以一個整數n(n<1000)開頭，後跟n對選手的比賽結果，比賽結果以一對選手名字（中間隔一空格）表示，前者戰勝後者。如果n為0，則表示輸入結束。   Output 對於每個選手群，若你判斷出產生了冠軍，則在一行中輸出“Yes”，否則在一行中輸出“No”。   Sample Input 3 Alice Bob Smith John Alice Smith 5 a c c d d e b e a d 0   Sample Output Yes No  

import java.io.*;  
import java.util.*;  
public class Main {  
    int t,n,cet;  
    int[] degree=new int[1001];  
    HashMap<String,Integer> hm=new HashMap<String, Integer>();  
    public static void main(String[] args) {  
        new Main().work();  
    }  
    void work(){  
        Scanner sc=new Scanner(new BufferedInputStream(System.in));  
        while(sc.hasNext()){  
            t=sc.nextInt();  
            if(t==0) break;  
              
            init();  
            //給每個字符串標號  
            for(int i=0;i<t;i++){  
                String s1=sc.next();  
                if(!hm.containsKey(s1)){  
                    hm.put(s1,n);  
                    n++;  
                }  
                String s2=sc.next();  
                if(!hm.containsKey(s2)){  
                    hm.put(s2,n);  
                    n++;  
                }  
                union(hm.get(s1),hm.get(s2));  
            }  
              
            cet=0;  
            for(int i=0;i<n;i++){  
                if(degree[i]==0)  
                    cet++;  
            }  
  
            if(cet==1)  
                System.out.println("Yes");  
            else  
                System.out.println("No");  
        }  
    }  
    void init(){  
        n=0;  
        hm.clear();  
        Arrays.fill(degree,0);  
    }  
    void union(int a,int b){      
        degree[b]++;//a贏了b, a->b, b的入度加1  
  
    }  
  
}