题目训练网址： https://vjudge.net/contest/247051
并查集是一种树型的数据结构，用于处理一些不相交集合 （Disjoint Sets）的合并及查询问题。常常在使用中以森林来 表示。
集就是让每个元素构成一个单元素的集合，也就是按 一定顺序将属于同一组的元素所在的集合合并。。
在一些有N个元素的集合应用问题中，我们通常是在开始时 让每个元素构成一个单元素的集合，然后按一定顺序将属于 同一组的元素所在的集合合并，其间要反复查找一个元素在 哪个集合中。这样的问题看起来似乎很简单，每次直接暴力 查找即可，但是我们需要注意的问题是，在数据量非常大的 情况下，那么时间复杂度将达到O（N*n）(n为查询次数)， 那么这类问题在实际应用中，如果采取上述方法去做的话， 耗费的时间将是巨大的。而如果用常规的数据结构去解决该 类问题的话（顺序结构，普通树结构等），那么计算机在空 间上也无法承受。所以，并查集这种数据结构便应运而生 了。
话说江湖上散落着各式各样的大侠，有上千个之多。整天背着剑在外面走来走去，碰到不是一路人的，就要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，都认为是自己人。这样，江湖上就形成了一个个群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？
我们可以在每个朋友圈内推举出一个有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。
但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通
的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错
敌友关系就好了。于是，门派产生了。
下面我们来看并查集的实现。int pre[1000] 这个数组，记录了每个大侠的上级是谁。大侠们从1开始编号，pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的。。每个人都只认自己的上级。find这个函数就是找掌门用的，意义再清楚不过了。
int find ( int x )
{
int r = x;
while (pre[r] !=r )
r = pre[r] ;
return r ;
} 那么，还有一个问题，怎么把记录门派记录下来，当两人成为朋友时，他们所在的门派也全都是朋友的朋友了，这个时候，我们只要找到他们的掌门，把其中一个的掌门改成另一个（原来是他本身），这样两个门派就变成一个门派了。
inline void join( int a, int b ) // 合并
{
int fa = find(a);
int fb = find(b);
if( fa != fb )
pre[fa] = fb;
} 建立门派的过程是用join函数两个人连接起来的，谁当谁的手下随机。路径压缩就是把所有人的上级直接指向掌门，这
样可以减少处理的范围。
inline int find( int x ) // 查询
{
int r = x;
while( pre[r] != r )
r = pre[r];
/* // 压缩路径的写法，加上更快
int i = x, tmp;
while( i != r )
{
tmp = pre[i];
pre[i] = r;
i = tmp;
}
*/
return r;
} 看两道例题
畅通工程
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
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
Huge input, scanf is recommended.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+7;
int n, m;
int pre[MAXN];
int find( int x )
{
int r = x;
while( pre[r] != r )
r = pre[r];
return r;
}
int main()
{
while( scanf("%d%d", &n, &m), n )
{
for( int i=0; i<=n; i++ )
pre[i] = i;
int v1, v2;
int ans = n-1; // 初始n个点，一共要连n-1条路
for( int i=1; i<=m; i++ )
{
scanf("%d%d", &v1, &v2);
v1 = find(v1);
v2 = find(v2);
if( v1 != v2 ) // 如果不在一个集合内，则连接的路数减一
{
pre[v1] = v2;
ans --; // 其实减去的是已经连接的路数，最后剩下的就是需要修的路
}
}
printf("%d\n", ans);
// 下面这种方法更好理解
/* int sum = 0;
for( int i=1; i<=n; i++ )
if( pre[i] == i ) // 可能还有很多小门派，因为需要统一所以还是自成一派的需要修一条路
sum++;
printf("%d\n", sum-1); */
}
return 0;
}
在并查集的基础上，对其中的每一个元素赋有某些值。在对并查集进行路径压缩和合并操作时，这些权值具有一定属
性，在这种情况下，需要对程序进行一些改动（视情况而定），常将他们与父节点的关系，变化为与所在树的根结点
关系。例如下题
还是畅通工程
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
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
题解： 先把所有边按从小到大的顺序排序。然后，逐个选取，在选取的过程中，如果查询到两个端点不在同一个集合，那么必然选择它作为最小生成树的一部分，并合并这两个端点。如果查询到这两个端点在同一个集合里，那么继续选取下一
条边，直至选取了n-1条边，算法结束。算法复杂度为排序的复杂度。O(e*log(e))
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100+7;
int n, m;
struct node{
int a, b, c; // a 到 b 有一条距离为C 的边
};
struct node road[MAXN*MAXN >> 1]; // 之前这里写成了 MAXN << 1 / 2 一直超时，错误的写法
bool cmp( struct node r1, struct node r2 )
{
return r1.c < r2.c;
}
int pre[MAXN];
inline int find( int x ) // 查询
{
int r = x;
while( pre[r] != r )
r = pre[r];
/* // 压缩路径的写法，加上更快，不加也能过
int i = x, tmp;
while( i != r )
{
tmp = pre[i];
pre[i] = r;
i = tmp;
}
*/
return r;
}
inline void join( int a, int b ) // 合并
{
int fa = find(a);
int fb = find(b);
if( fa != fb )
pre[fa] = fb;
}
inline void init()
{
for( int i=0; i<MAXN; i++ )
pre[i] = i;
}
int main()
{
while( scanf("%d", &n), n )
{
m = n * (n-1) / 2;
for( int i=0; i<m; i++ )
scanf("%d%d%d", &road[i].a, &road[i].b, &road[i].c);
sort(road, road+m, cmp);
init();
int sum = 0;
int cnt = 0;
int tmp1, tmp2;
for( int i=0; i<m; i++ )
{
tmp1 = road[i].a;
tmp2 = road[i].b;
if( find(tmp1) != find(tmp2) )
{
join(tmp1, tmp2);
sum += road[i].c;
cnt++;
if( cnt == n-1 )
break;
}
}
printf("%d\n", sum);
}
return 0;
}
更多例题代码
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
//#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
const int MAXN = (int)3e4 + 7;
int n, m;
int pre[MAXN];
int sum[MAXN];
int find( int x )
{
int r = x;
while( pre[r] != r )
r = pre[r];
int i = x, tmp;
/* // 路径压缩
while( pre[i] != r )
{
tmp = pre[i];
pre[i] = r;
i = tmp;
}
*/
return r;
}
int join( int a, int b )
{
int fa = find(a); // 第一个数对应的根节点
int fb = find(b);
if( fa != fb )
{
pre[fb] = fa; // 以第一个数的根节点作为根节点
sum[fa] += sum[fb]; // 第一个数对应的根节点对应的个数
}
}
void init()
{
for( int i=0; i<MAXN; i++ )
pre[i] = i, sum[i] = 1;
}
int main()
{
while( scanf("%d%d", &n, &m), (n || m) )
{
init();
while( m-- )
{
int k, num, num2;
scanf("%d", &k); // 该组有多少个数
scanf("%d", &num); // 该组中的第一个数
for( int i=1; i<k; i++ )
{
scanf("%d", &num2);
join(num, num2); // 每组数（不包括k）中第一个数的根节点作为该组数的根节点
}
}
printf("%d\n", sum[find(0)]);
}
return 0;
}
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
//#include <bits/stdc++.h>
#include <stdio.h>
#include <set>
using namespace std;
const int MAXN = (int) 5e4+7;
int pre[MAXN];
void init()
{
for( int i=0; i<MAXN; i++ )
pre[i] = i;
}
int find( int x )
{
int r = x;
while( pre[r] != r )
r = pre[r];
int i = x, tmp;
while( i != r )
{
tmp = pre[i];
pre[i] = r;
i = tmp;
}
return r;
}
void join( int a, int b )
{
int fa = find(a);
int fb = find(b);
if( fa != fb )
pre[fa] = fb;
}
set<int> s;
int main()
{
int n, m;
int t = 0;
while( ~scanf("%d%d", &n, &m) )
{
if( n == 0 && m == 0 ) break;
init();
t ++;
//m = n * (n-1) / 2;
int x, y;
for( int i=0; i < m; i++ )
{
scanf("%d%d", &x, &y);
if( find(x) != find(y) )
join(x, y);
}
s.clear();
for( int i=1; i<=n; i++ )
{
int tmp = find(i);
if( !s.count(tmp) )
s.insert(tmp);
}
printf("Case %d: %d\n", t, s.size());
}
return 0;
}
都是简单的模板题，给出的代码可以做模板使用。
京公网安备 11010502036488号