擒贼先擒王(并查集)
目录题面
快过年了,犯罪分子也开始为年终奖奋斗了。晓哼的家乡出现了多次抢劫事件。由于强盗人数过于庞大,作案频繁,警方想查清楚到底有几个犯罪团伙实在太不容易了,不过警察叔叔还是搜集到了一些线索,需要咱们帮忙分析一下:
现在有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;
}
标签:int,查集,样例,强盗,擒贼先擒王,同伙
From: https://www.cnblogs.com/L-1115/p/17574649.html