thesuspects.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 83 行

package PKU.Unionfindsets;
import java.util.Scanner;


/**
 * ID:1611
 * 并查集算法
 * @author yhm
 *
 */
public class TheSuspects {

	
	static int[] num ,father;
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int n = cin.nextInt();
			int m = cin.nextInt();
			if(n==0 && m==0){
				break;
			}
			makeset(n);
			for(int i=0;i<m;i++){
				int k = cin.nextInt();
				int mem1 = cin.nextInt();
				for(int j=1;j<k;j++){
					int mem = cin.nextInt();
					unionset(mem1,mem);
				}
			}
			
			System.out.println(num[find(0)]);
			
			
		}

	}
	
	static void makeset(int n)
	{
		num = new int[n];
		father = new int[n];
	    for(int i=0;i<n;i++)
	    {
	        father[i]=-1;
	        num[i]=1;
	    }
	}

	static int find(int a)
	{
	    while(father[a]!=-1)
	        a=father[a];
	    return a;
	}

	static void unionset(int a,int b)
	{
		a = find(a);
		b = find(b);
	    if(a==b)
	        return;
	    if(num[a]<=num[b])
	    {
	        father[a]=b;
	        num[b]+=num[a];
	    }
	    else
	    {
	        father[b]=a;
	        num[a]+=num[b];
	    }
	}
	

}