HDU1856（More is better）—並查集+樹

[java] 
package D0813; 
/*
 * 題目大意：mr wang把一群小孩放在一個房間裡，這群小孩有些之間是朋友，
 * mr wang每次要從小孩中選出一些離開這個房間，問你最後留下的最多有幾個小孩（小孩之間必須是朋友關系，
 * 可以使直接的也可以是節間的），給出直接的朋友關系，要你確定最的留下的小孩子的數目
 * 思路：並查集》找出集合數最多的就是結果
 * */ 
import java.io.*; 
public class HDU1856 { 
    static int[]set; 
    static int[]height ; 
    static int[]boy;//節點數。 
    static int max; 
    public static void main(String[] args) throws IOException { 
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); 
        while(st.nextToken()!=StreamTokenizer.TT_EOF){ 
            int n = (int)st.nval; 
            init(n); 
            max = 1;//一定要注意這個地方，不能使0.因為最後至少可以留下一個小孩 
            for(int i = 0;i<n;i++){ 
                st.nextToken(); 
                int s = (int)st.nval; 
                st.nextToken(); 
                int e = (int)st.nval; 
                merge(s,e); 
            } 
            System.out.println(max); 
        } 
    } 
 
    public static void init(int n){ 
        boy = new int[2*n+1]; 
        height = new int[2*n+1]; 
        set = new int[2*n+1]; 
        for(int i = 1;i<=2*n;i++){ 
            set[i] = i; 
            height[i] = 1; 
            boy[i] = 1; 
        } 
    } 
    public static int find(int x){ 
        int son,temp ; 
        son = x; 
        while(x!=set[x]) 
            x = set[x]; 
        //路徑壓縮，可以不壓縮 
        while(son!=x){ 
            temp = set[son]; 
            set[son] = x; 
            son = temp; 
        } 
        return x; 
    } 
    public static void merge(int a,int b){ 
        a = find(a); 
        b = find(b); 
        if(a!=b){ 
            if(height[a]>height[b]){ 
                set[b] = a; 
                boy[a]+= boy[b]; 
                max = Math.max(max, boy[a]); 
            } 
            else if(height[a]<height[b]){ 
                set[a] = b; 
                boy[b]+= boy[a]; 
                max = Math.max(max, boy[b]); 
            } 
            else{ 
                set[b] = a; 
                height[a]++; 
                boy[a]+= boy[b]; 
                max = Math.max(max, boy[a]); 
            } 
        } 
    } 
}