并查集（求有多少个团伙）
【基本概念】
并查集通过一个一维数组来实现，其本质是维护一个森林。刚开始的时候，森林的每个点都是孤立的，每个人都是自己的王，也可以理解为每个点就是一颗只有一个结点的树，之后通过一些条件，逐渐将这些树合并成一棵大树。
其实合并的过程就是一个“认爹的过程”。在这个过程中，要遵守“靠左”原则和”擒贼先擒王“原则（这里靠左或者靠右都并无大碍，但一旦选择一个原则，便要一直遵循）
在每次判断两个结点是否以及在同一棵树上的时候（一棵树其实就是一个集合），也要注意必须求其根源，中间父结点是不能说明问题的，必须找到其祖宗（树的根结点），判断两个结点的祖宗是否是同一个根结点才行。
【问题描述】
第一行两个数：n，m。其中n表示强盗的个数，m表示警方搜集到的线索。
接下来m行，每行两个整数a，b表示a强盗和b强盗是同伙。
问一共有多少个团伙？
【样例输入】
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
【样例输出】
3
【程序代码】
#include <bits/stdc++.h>
using namespace std;
int pre[100];
int find(int x) { //寻找x的父节点
if(x!=pre[x])
pre[x]=find(pre[x]);
return pre[x];
}
void merge(int x,int y) { //合并两个子集
if(find(x)!=find(y)) {
pre[find(y)]=find(x);
}
}
int main() {
int u,v,p,q;
int ans;
cin>>u>>v; //顶点数、边数
for(int i=1; i<=u; i++) //初始时每个节点的父节点都是自己
pre[i]=i;
for(int i=0; i<v; i++) {
cin>>p>>q; //边的两个顶点序号
merge(p,q);
}
for(int i=1; i<=u; i++) {
if(find(i)==i)
ans++; //计算连通子图个数，也就是得出几个团伙
}
cout<<ans<<endl;
return 0;
}
评论