并查集(模板)

蔚落 2023-06-01 06:11 11阅读 0赞

# 并查集(模板) #

[来源][Link 1]

并查集：将不同分散的结点，通过某种关系将他们连接成一个森林  
并查集分为3步：

1. 并：给出两点关系，如果属于同一集合，进行merge
    2. 查：在合并时，需要先写出查，即找到该点的祖先点
    3. 集：merge后，将新加入的点的祖先点更新

## 示例 ##

已知强盗同伙信息，求存在多少个犯罪团伙

**Input**  
10 9  
1 2  
3 4  
5 2  
4 6  
2 6  
8 7  
9 7  
1 6  
2 4

第一行表示10个强盗，9条信息  
后面9行 - a b：表示强盗a与强盗b为同伙（同伙的同伙也是同伙）

思路：使用一个一维数组下标表示强盗的编号，下标对应的值就表示强盗的boss，依据“靠左”原则（以强盗a作为强盗b的boss），如果一个强盗存在boss，那么就直接让这个boss与强盗同伙进行比较（“靠左”原则）

例如：下一条信息为 2 6，那么需要找到2的boss和6的boss，根据“靠左”原则将他们合并  
![1564145-20190808150155275-560870498.png][]

![1564145-20190808150203680-1843907696.png][]

经过合并之后就得到了上面的图，至于为什么6会直接与5相连，这块就存在了一个路径压缩的方法，这也是优化了搜索祖结点的时间

## 代码 ##

#include <stdio.h> #include <iostream> #include <algorithm> using namespace std; int parent[1000],n,m,sum; //parent数组存储的是每个强盗的父亲即boss、sum用来记录犯罪团伙的数量 void Init() { for(int i = 1;i <= n;i++) parent[i] = i; return; } int get_boss(int v) { if(parent[v] == v) return v; else { //路径压缩(使搜索祖宗的过程中，路径中搜索的结点的父亲的变为祖宗) parent[v] = get_boss(parent[v]); return parent[v]; } } void Merge(int v,int u) { int t1 = get_boss(v); int t2 = get_boss(u); parent[t2] = t1; return; } int main() { int i,a,b; scanf("%d %d",&n,&m); //初始化，让每个强盗的父亲都是自己 Init(); for(i = 0;i < m;i++) { scanf("%d %d",&a,&b); Merge(a,b); } //遍历parent数组，如果强盗的父亲还是自己，那么就是一个犯罪团伙 for(i = 1;i <= n;i++) { if(parent[i] == i) sum++; } printf("%d\n",sum); return 0; }

转载于:https://www.cnblogs.com/tttfu/p/11321227.html

[Link 1]: https://blog.csdn.net/qq_43327091/article/details/88085075
[1564145-20190808150155275-560870498.png]: /images/20230601/c3a718314c7e4aa6923f444d9da51c80.png
[1564145-20190808150203680-1843907696.png]: /images/20230601/c8d09a9f229b4393b9fae3b37b1ba405.png