并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询
问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定
顺序将属于同一组的元素所在的集合合并。。
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的
集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个
集合中。这样的问题看起来似乎很简单，每次直接暴力查找即可，但是我们需要注意的问题
是，在数据量非常大的情况下，那么时间复杂度将达到O（N*n）(n为查询次数)，那么这类问
题在实际应用中，如果采取上述方法去做的话，耗费的时间将是巨大的。而如果用常规的数据
结构去解决该类问题的话（顺序结构，普通树结构等），那么计算机在空间上也无法承受。所
以，并查集这种数据结构便应运而生了。
题目链接：
vjudge.net/contest/247051
（入门题是B题哦）
A – The Suspects
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
Input
The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
Sample Input
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0
Sample Output
4 1 1
这道题有一个难点，怎样判断多个人的感染情况，这里我们先把第一个默认队长，然后后边的以此和队长进行join。
这里是原版链接哦：
点我
#include <cstdio>
using namespace std;
const int maxn = 3e4 + 5;
int pre[maxn];
int find(int x)
{
// int r = x;
// while(pre[r] != r)
// r = pre[r];
return pre[x] == x ? x : find(pre[x]);
//查询操作：返回的是x的根结点
// int i = x, j;
// while(i != r)
// {
// j = pre[i];
// pre[i] = r;
// i = j;
// }
// return r;
}
void join(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx == 0)
{
pre[fy] = fx;
}
else if(fy == 0)
pre[fx] = fy;
else
pre[fx] = fy;
}
int main()
{
int n, m, ans, i, j, k, fir, get;
while(scanf("%d%d", &n, &m), n||m)
{
ans = 0;
for(i = 0; i < n; i++)
{
pre[i] = i;
}
for(i = 1; i <= m; i++)
{
scanf("%d%d", &k, &fir);
for(j = 1; j < k; j++)
{
scanf("%d", &get);
join(get, fir);
}
}
for(i = 0; i < n; i++)
{
if(find(i) == 0)
ans++;
}
printf("%d\n", ans);
}
return 0;
}
B – 畅通工程
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0
Sample Output
1 0 2 998
基础板子题。
#include <cstdio>
using namespace std;
const int maxn = 3e4 + 5;
int pre[maxn];
int find(int x)
{
// int r = x;
// while(pre[r] != r)
// r = pre[r];
return pre[x] == x ? x : find(pre[x]);
//查询操作：返回的是x的根结点
// int i = x, j;
// while(i != r)
// {
// j = pre[i];
// pre[i] = r;
// i = j;
// }
// return r;
}
void join(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx == 0)
{
pre[fy] = fx;
}
else if(fy == 0)
pre[fx] = fy;
else
pre[fx] = fy;
}
int main()
{
int n, m, ans, i, j, k, fir, get;
while(scanf("%d%d", &n, &m), n||m)
{
ans = 0;
for(i = 0; i < n; i++)
{
pre[i] = i;
}
for(i = 1; i <= m; i++)
{
scanf("%d%d", &k, &fir);
for(j = 1; j < k; j++)
{
scanf("%d", &get);
join(get, fir);
}
}
for(i = 0; i < n; i++)
{
if(find(i) == 0)
ans++;
}
printf("%d\n", ans);
}
return 0;
}
C – 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.
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.
Sample Input
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
Sample Output
Case 1: 1 Case 2: 7
最后那个for有点意思，当find(i) == i时，自己就是老大，那当然也表示着有多少个宗教啦。
#include <cstdio>
using namespace std;
const int maxn = 5e4 + 5;
int pre[maxn];
int find(int x)
{
// int r = x;
// while(pre[r] != r)
// r = pre[r];
return pre[x] == x ? x : find(pre[x]);
//查询操作：返回的是x的根结点
// int i = x, j;
// while(i != r)
// {
// j = pre[i];
// pre[i] = r;
// i = j;
// }
// return r;
}
void join(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx != fy)
pre[fx] = fy;
}
int main()
{
int n, m, ans, i, j, k, cnt = 1;
while(scanf("%d%d", &n, &m), n||m)
{
ans = 0;
for(i = 1; i <= n; i++)
{
pre[i] = i;
}
for(i = 1; i <= m; i++)
{
scanf("%d%d", &j, &k);
join(j, k);
}
for(i = 1; i <= n; i++)
{
if(find(i) == i)
{
ans++;
}
}
printf("Case %d: %d\n", cnt++, ans);
}
return 0;
}
D – 还是畅通工程
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
Sample Output
3 5
这题WA了很多次，原因竟是sort排序写成a+1+n???
这里加个原版链接：
点我
#include <bits/stdc++.h>
using namespace std;
int pre[103];
struct node
{
int x, y, z;
}a[5000];
bool cmp(node a, node b)
{
return a.z < b.z;
}
int findd(int x)
{
// int r = x;
// while(pre[r] != r)
// r = pre[r];
return pre[x] == x ? x : findd(pre[x]);
//查询操作：返回的是x的根结点
// int i = x, j;
// while(i != r)
// {
// j = pre[i];
// pre[i] = r;
// i = j;
// }
// return r;
}
//void join(int x, int y)
//{
// int fx = find(a[i]), fy = find(y);
// if(fx != fy)
// {
// pre[fx].id = fy;
// ans += pre[fx].dis;
// }
//
//}
int main()
{
int n, m, ans, i, b, c;
while(scanf("%d", &n), n)
{
ans = 0;
m = n*(n-1)/2;
for(i = 1; i <= n; i++)
{
pre[i] = i;
}
for(i = 1; i <= m; i++)
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
}
sort(a+1, a+1+m,cmp);
for(i = 1; i <= m; i++)
{
b = findd(a[i].x);
c = findd(a[i].y);
if(b == c) continue;
pre[c] = b;
ans += a[i].z;
}
printf("%d\n", ans);
}
return 0;
}
G – How Many Tables
Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
Input
The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.
Output
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
Sample Input
2 5 3 1 2 2 3 4 5 5 1 2 5
Sample Output
2 4
这道题巨坑啊啊啊，一直PE贼难受，怀疑人参。（其实就是最好加个getchar()，没那么多花里胡哨的。）
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e3 + 5;
int pre[maxn];
int find(int x)
{
// int r = x;
// while(pre[r] != r)
// r = pre[r];
return pre[x] == x ? x : find(pre[x]);
//查询操作：返回的是x的根结点
// int i = x, j;
// while(i != r)
// {
// j = pre[i];
// pre[i] = r;
// i = j;
// }
// return r;
}
void join(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx != fy)
pre[fx] = fy;
}
int main()
{
int t, n, m, ans, i, j, k;
cin>>t;
while(t--)
{
scanf("%d%d", &n, &m);
ans = 0;
for(i = 1; i <= n; i++)
{
pre[i] = i;
}
for(i = 1; i <= m; i++)
{
scanf("%d%d", &j, &k);
join(j, k);
}
for(i = 1; i <= n; i++)
{
if(find(i) == i)
{
ans++;
}
}
printf("%d\n", ans);
getchar();
}
return 0;
}