| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为何总是WA呢?--------郁闷,第一次写并查集#include<iostream>
using namespace std;
int rank[30001];
int cluster[30001];
int findCluster(int pos)
{
if(cluster[pos]==pos)
{
return pos;
}
return cluster[pos]=findCluster(cluster[pos]);
}
void Merge(int i1,int i2)
{
int j1=findCluster(i1);
int j2=findCluster(i2);
if(j1==j2)
return;
if(rank[j1]>rank[j2])
{
cluster[i2]=j1;
}
else
{
cluster[i1]=j2;
if(rank[j1]==rank[j2])
{
rank[j2]++;
}
}
}
//利用并查集来解POJ1611问题
void func(int N,int K)
{
//看了蜗居,人生真是艰难
//初始化
for(int i=0;i<30001;i++)
cluster[i]=i;
for(int i=0;i<30001;i++)
rank[i]=0;
for(int k=0;k<K;k++)
{
int temp;
cin>>temp;
int temp1;
cin>>temp1;
for(int i=1;i<temp;i++)
{
int temp2;
cin>>temp2;
Merge(temp1,temp2);
}
}
int sum=0;
for(int i=0;i<N;i++)
{
if(findCluster(i)==findCluster(0))
{
sum++;
}
}
cout<<sum<<endl;
}
int main()
{
int N,K;
cin>>N;
cin>>K;
while(true)
{
if(N==0&&K==0)
{
break;
}
if(K==0)
{
cout<<"1"<<endl;
}
else
{
func(N,K);
}
cin>>N>>K;
}
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator