Ubiquitous Religions

http://acm.pku.edu.cn/JudgeOnline/problem?id=2524

Description

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.

Input

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.

Output

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

Source

Alberta Collegiate Programming Contest 2003.10.18


Solving

어느 한 대학교에 다니는 학생들에세 설문조사를 하여 이 학교내에 최대한 몇 개의 종교가 존재하는지 알아보고자 한다. 같은 종교를 가진 두 명의 학생의 번호가 인풋으로 주어지면 학교내에 존재 가능한 최대의 종교의 수를 구하여라.

Connected Component 문제로 해석할 수 있다. 학생을 그래프상의 정점으로 보고 두 학생이 같은 종교를 가지고 있다면 두 정점간에 연결성이 있는 것으로 볼 수 있다. 그래프를 구성한 후 Connected Component의 갯수를 구하는 것으로 문제를 해결할 수 있다. Connected Component는 간단하게 DFS나 BFS로 구현할 수 있고, 아래의 소스에서 사용한 것처럼 서로소집합 자료구조를 사용하여 빠르게 구할 수 있다.

서로소집합 자료구조는 대표적으로 최소신장트리를구하는 크루스칼알고리즘에서 사용된다.

#include <cstdio> #include <cstdlib> #include <memory> #define min(a,b) (((a) < (b)) ? (a) : (b)) int D[50002]; int main() { int i; int n, m; int a, b, c, d; int count = 0; int T = 0; while (scanf("%d%d", &n, &m) > 0) { if (n == 0 && m == 0) break; memset(D, 0x00, sizeof(D)); count = 0; for (i = 1; i <=n; i++) D[i] = i; for (i = 0; i < m; i++) { scanf("%d%d", &a, &b); c = a; d = b; while (D[c] != c) c = D[c]; while (D[d] != d) d = D[d]; D[a] = D[b] = min(D[c], D[d]); D[c] = D[d] = min(D[c], D[d]); } for (i = 1; i <= n; i++) if (D[i] == i) count++; printf("Case %d: %d\n", ++T, count); } return 0; }