当前位置: 代码迷 >> 综合 >> POJ1611 The Suspects (求x所在集合的大小)
  详细解决方案

POJ1611 The Suspects (求x所在集合的大小)

热度:56   发布时间:2023-11-22 00:39:15.0

题目链接

http://poj.org/problem?id=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

分析

直接套用并查集维护每一个集合。
最后枚举每一个人看其与0号是否在一个集合中。

AC代码

//16ms 0.4MB
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=3e4+100;
int par[maxn],n,m;
void init()
{for(int i=0;i<=n;i++) par[i]=i;
}
int find(int x)
{return par[x]==x?x:par[x]=find(par[x]);
}
void unit(int x,int y)
{par[find(x)]=find(y);
}
bool same(int x,int y)
{return find(x)==find(y);
}
int a[maxn];
int main()
{while(~scanf("%d%d",&n,&m)){if(n==0 && m==0) break;init();while(m--){int k;scanf("%d",&k);for(int i=1;i<=k;i++)scanf("%d",&a[i]);for(int i=1;i<k;i++)if(!same(a[i],a[i+1])) unit(a[i],a[i+1]);}int ans=0;for(int i=0;i<n;i++)if(same(0,i)) ans++;printf("%d\n",ans);}return 0;
}