2013
11-11

# Ubiquitous Religions

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.

You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.

For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.

10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0


Case 1: 1
Case 2: 7


Huge input, scanf is recommended.

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
final int MAXSIZE = 50001;
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int caseI = 1;
int max = 0;
while (scan.hasNext()) {
int n = scan.nextInt();
int m = scan.nextInt();
if (n == 0 && m == 0) {
break;
}
DisjointSet dj = new DisjointSet(MAXSIZE);
int count = 0;
for (int i = 0; i < m; i++) {
int a = scan.nextInt();
int b = scan.nextInt();
int ra = dj.find(a);
int rb = dj.find(b);
if (ra != rb) {
dj.union(ra, rb);
count++;
}
}
max = n - count;
String result = "Case " + caseI + ": " + max;
System.out.println(result);
caseI++;
}
}
}

class DisjointSet {

protected int n;
protected int[] parent;
protected int[] rank;

public DisjointSet(int n) {
this.n = n;
init(n);
}

protected void init(int n) {
this.parent = new int[this.n + 1];
this.rank = new int[this.n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 1;
}
}

protected int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

protected void union(int ra, int rb) {
if (rank[ra] > rank[rb]) {
parent[rb] = ra;
} else if (rank[ra] < rank[rb]) {
parent[ra] = rb;
} else {
rank[rb]++;
parent[ra] = rb;
}
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。

4. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的