| ||||||||||
| 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 | |||||||||
变异并查集<附代码>#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 30010
long int father[MAX];
long int s[MAX];
int flag[MAX];
long int finds(long int x)
{
if(x!=father[x])
{
father[x]= finds(father[x]);
}
return father[x];
}
int main()
{
long int i,j,m,n,k,q,mas;
while(scanf("%ld %ld",&m,&n)&&(n||m))
{
memset(flag,0,sizeof(flag));
q= 0;
for(i= 0;i<m;i++)
{
father[i]= i;
}
for(i=0;i<n;i++)
{
mas= 30001;
scanf("%ld",&k);
for(j=0;j<k;j++)
{
scanf("%ld",&s[j]);
flag[s[j]]= 1;
if(mas>finds(s[j]))
{
mas= finds(s[j]);
}
}
for(j=0;j<k;j++)
{
father[finds(father[s[j]])]= mas;
}
}
flag[0]= 1;
for(i= 1;i<m;i++)
{
if(flag[i])
father[i]= finds(i);
}
for(i=0;i<m;i++)
{
if(flag[i])
{
if(father[i]==0)
{
q++;
}
}
}
printf("%ld\n",q);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator