poj 2524 并查集

第二次初探并查集，poj2524，一次AC，挺高兴的，呵呵！

ps：这道题是求在一个大学里面有的学生信仰多少个不同的宗教，注意一点就是下面没出现的学生，视为他们各自信仰不同的宗教。

import java.util.Scanner;

public class Main{
	static int[] r;
	//static int[] rank;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int casenumber = 0;
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if (n == 0 && m == 0)
				break;
			casenumber++;
			r = new int[n + 1];
			//rank = new int[n + 1];
			//Arrays.fill(rank, 1);
			for (int i = 1; i <= n; ++i) {
				r[i] = i;
			}
			for (int i = 0; i < m; ++i) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				merge(x, y);
			}
			int ans = 0;
			// TreeSet<Integer> re = new TreeSet<Integer>();
			int[] re = new int[n + 1];
			for (int i = 1; i <= n; ++i) {
				if (r[i] == i) {
					if (re[i] == 0) {
						++ans;
						re[i] = 1;
					}

				} else {
					if (re[find(i)] == 0) {
						++ans;
						re[i] = 1;
					}
				}
			}
			System.out.println("Case " + casenumber + ": " + ans);
		}

	}

	static void merge(int x, int y) {
		int px = find(x);
		int py = find(y);

		if (px == py)
			return;
		// System.out.println(rank[px]+";"+rank[py]);
		if (px <= py) {
			r[py] = px;
			// rank[px] = rank[py] + rank[px];

		} else {
			r[px] = py;
			// rank[py] = rank[py] + rank[px];
			// /System.out.println(rank[py]);
		}
	}

	static int find(int x) {

		if (r[x] == x)
			return x;

		return find(r[x]);
	}
}