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]); 
            } 
        } 
    } 
} 

补充：软件开发 , C++ ,

上一个：hdu 1401
下一个：淘宝技术类2011年校招笔试题