ubiquitousreligions.java

PKU中一些数据结构基本算法题的java实现

import java.util.Scanner;


/**
 * ID:2524
 * 并查集
 * @author yhm
 *
 */
public class UbiquitousReligions {

	static ReligionNode[] religions;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseID=1;
		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 x = cin.nextInt()-1;
				int y = cin.nextInt()-1;
				union(x,y);
			}
			int sum=0;
			for(int i=0;i<n;i++){
				if(religions[i].parent==-1){
					sum++;
				}
			}

			System.out.println("Case "+caseID+": "+sum);
			caseID++;
			
			
		}

	}
	
	static void makeSet(int n){
		religions = new ReligionNode[n];
		for(int i=0;i<n;i++){
			religions[i] = new ReligionNode(0,-1);
		}
	}
	
	static int find(int x){
		int temp = x;
		while(religions[x].parent!=-1){
			x = religions[x].parent;
		}
		int result = x;
		x = temp;
		while(religions[x].parent!=-1){
			temp = religions[x].parent;
			religions[x].parent = result;
			x = temp;
		}
		return result;
	}
	
	static void union(int x, int y){
		x = find(x);
		y = find(y);
		if(x==y){
			return;
		}
		if(religions[x].rank>religions[y].rank){
			religions[y].parent = x;
			religions[x].rank += religions[y].rank;
		}
//		else if(religions[x].rank<religions[y].rank){
//			religions[x].parent = y;
//		}
		else{
			religions[x].parent = y;
			religions[y].rank += religions[x].rank;
		}
	}

}


class ReligionNode{
	int rank;
	int parent;
	public ReligionNode(int rank, int parent) {
		super();
		this.rank = rank;
		this.parent = parent;
	}
	
}