POJ-1611(并查集)
警察抓贩毒集团。有不同类型的犯罪集团，人员可能重复，集团内的人会相互接触。现在警察在其中一人（0号）身上搜出毒品，认为与这个人直接接触或通过其他人有间接接触的人都是嫌疑犯。问包括0号犯人共有多少嫌疑犯？
Input
多样例输入。
每个测试用例以两个整数n和m开头，其中n为人数，m为犯罪集团数。你可以假定0 < n <= 30000和0 <= m <= 500。在所有的情况下，每个人都有自己独特的整数编号0到n−1, 且0号是公认的嫌疑犯。
接下来m行输入，每个犯罪集团一行。每一行从一个整数k开始，它本身表示集团内成员的数量。按照成员的数量，在这个组中有k个整数表示人员。一行中的所有整数都被至少一个空格隔开。
n = 0且m = 0时输入结束。
Output
对于每个样例，输出嫌疑犯人数。
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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; const int maxn=30010; int fa[maxn],cnt[maxn]; int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); //最好是这样写 换了中写法有误自己看不出来哪里错了 return fa[x]; } void unionn(int x,int y) { if(find(x)==find(y)) return; cnt[find(x)]+=cnt[find(y)]; fa[find(y)]=find(x); } int main() { int n,m,k,a,a1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; for(int i=0;i<n;i++) { fa[i]=i; cnt[i]=1;//记嫌疑犯人数 } while(m--) { scanf("%d %d",&k,&a1); for(int j=1;j<k;j++) { scanf("%d",&a); unionn(a1,a); } } cout<<cnt[find(0)]<<endl; } }
就是找根节点 不断的合并 并更新根下的数量的值
复制代码
1
2
3
4
5
6
7void unionn(int x,int y) { if(find(x)==find(y)) return; cnt[find(x)]+=cnt[find(y)]; fa[find(y)]=find(x); }
很关键 寻找根结点编号并压缩路径 比起直接相连 大大减少时间复杂度
最后
以上就是曾经皮带最近收集整理的关于The-suspects-POJ-1611(并查集)的全部内容，更多相关The-suspects-POJ-1611(并查集)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复