题目链接:http://poj.org/problem?id=1611
//非常基础的并查集 <wbr>可以参考<a href="http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.html"><span style="color:#744d22">http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.</span></a><a href="http://www.cnblogs.com/cherish_yimi/archive/2009/10/11/1580839.html"><span style="color:#744d22">html</span></a></wbr>
#include<iostream>
using namespace std;
int f[30000],rank[30000];
void makeset(int x)
{
int i;
for(i=0;i<x;i++)
f[i]=i,rank[i]=0;
}
int findset(int x)
{
if(x!=f[x])
f[x]=findset(f[x]);
return f[x];
}
void unionset(int a,int b)
{
int fa=findset(a);
int fb=findset(b);
if(rank[fa]>rank[fb])f[fb]=fa;
else
{
if(rank[fa]==rank[fb])rank[fb]++;
f[fa]=fb;
}
}
int main()
{
int n,m;
while(cin>>n>>m,n||m)
{
int cnt=1;//′ú±í?Dè?êy
int i,j;
makeset(n);
for(i=0;i<m;i++)
{
int t,a,b;
cin>>t;
cin>>a;
for(j=1;j<t;j++)
{
cin>>b;
unionset(a,b);
a=b;
}
}
int st=findset(0);
for(i=1;i<n;i++)
if(st==findset(i))
cnt++;
cout<<cnt<<endl;
}
return 0;
}
分享到:
相关推荐
poj 1611 The Suspects 代码 并查集的应用
poj 1611 The Suspects.md
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
这份代码用C++实现了经典算法并查集,来源于poj题目1182
并查集基础 acm 算法 poj oi 并查集基础.ppt
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
POJ1089 并查集可以解决 并查集加路径压缩
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
poj 3191 The Moronic Cowmpouter.md
poj 1989 The Cow Lineup.md
poj 3260 The Fewest Coins.md
poj 3901 The Computer Game.md
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
Net<br>Pku acm 3278 Catch That Cow<br>Pku acm 2253 Frogger<br>Pku acm 1062 昂贵的聘礼 Pku acm 1125 Stockbroker Grapevine Pku acm 1611 The Suspects Pku acm 2492 A Bug's Life 更多请访问:...
有多个任务一起开始执行,每个任务的时间不同,输出前n次的任务结果