首页 > 代码库 > POJ 1611 The Suspects
POJ 1611 The Suspects
并查集问题。
题意是说: 编号0 可能感染SARS。
然后有M个 团队,团队的人可能互相感染。
找出全部可能感染的SARS人。
把某个团队的并起来就好了。
最后扫描一遍。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int fa[30001]; int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } int main() { while(scanf("%d%d",&n,&m),n||m) { for(int i=0;i<=n;i++) fa[i]=i; while(m--) { int t,u,v; scanf("%d",&t); if(!t)continue; scanf("%d",&u); u=father(u); while(--t) { scanf("%d",&v); v=father(v); if(u==v)continue; fa[v]=u; } } int ans=0; int s=father(0); for(int i=0;i<=n;i++) if(father(i)==s)ans++; printf("%d\n",ans); } }
POJ 1611 The Suspects
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。