擒贼先擒王（并查集）
擒贼先擒王（并查集）
目录
- 擒贼先擒王（并查集）
- 题面
- 题目概括
- 思路
- AC代码和注释
题面
快过年了，犯罪分子也开始为年终奖奋斗了。晓哼的家乡出现了多次抢劫事件。由于强盗人数过于庞大，作案频繁，警方想查清楚到底有几个犯罪团伙实在太不容易了，不过警察叔叔还是搜集到了一些线索，需要咱们帮忙分析一下：
现在有10个强盗。
1号强盗与2号强盗是同伙。
3号强盗与4号强盗是同伙。
5号强盗与2号强盗是同伙。
4号强盗与6号强盗是同伙。
2号强盗与6号强盗是同伙。
8号强盗与7号强盗是同伙。
9号强盗与7号强盗是同伙。
1号强盗与6号强盗是同伙。
2号强盗与4号强盗是同伙。
有一点需要注意，强盗同伙的同伙也是同伙。你能帮助警方查出有多少个独立的犯罪团伙吗？
输入
第一行n m，n(n< 3000 )表示强盗的人数，m表示警方搜集到的m(m< 5000 )条线索。
接下来的m行每一行有两个数 a b。表示强盗a和强盗b是同伙。
输出
有多少个独立的犯罪团伙
样例
样例输入1
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
样例输出1
3
题目概括
我们要找出所有数据，依照题目关系条件，可以组成的树的棵数
思路
并查集不清楚的朋友看这儿
先按照输入建树，再统计有多少个结点的上级是它本身（根节点）
最后把它A掉
AC代码和注释
#include<bits/stdc++.h>
using namespace std;
int n,m;
int parent[5005];
void init(int n) {//初始化
for(int i = 1;i <= n;i ++) {
parent[i] = i;
}
}
int find(int t){//查找
if(parent[t] == t) return t;
else return parent[t] = find(parent[t]);
}
void merge(int r1,int r2){//合并
parent[find(r2)] = find(r1);
}
int main(){
cin >> n >> m;
init(n);
for(int i = 1;i <= m;i ++){
int x,y;
cin >> x >> y;
merge(x,y);
}
int ans = 0;
for(int i = 1;i <= n;i ++){//记录有多少个结点的上级是它本身（根节点）
if(parent[i] == i) ans ++;
}
cout << ans;
return 0;
}