| ||||||||||
| 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 <stdio.h>
int father[100010], kind[100010];
void makeset(int n)
{
int i;
for(i=1;i<=n;++i)
{
father[i]=i;
kind[i]=0;
}
}
int findset(int x)
{
int temp;
if(x!=father[x])
{
temp=father[x];
father[x]=findset(father[x]);
kind[x]=(kind[x]+kind[temp])%2;
}
return father[x];
}
void Union(int x, int y)
{
int xx, yy;
xx=findset(x);
yy=findset(y);
father[yy]=xx;
kind[yy]=(kind[x]-kind[y]+1)%2;
}
int main()
{
int T, N , M, ai, bi, aai, bbi, kk, tt, tag;
scanf("%d", &T);
for(kk=0;kk<T;++kk)
{
scanf("%d%d", &N, &M);
makeset(N);
tag=0;
for(tt=0;tt<M;++tt)
{
scanf("%d%d",&ai, &bi);
aai=findset(ai);
bbi=findset(bi);
if(aai!=bbi)
{
Union(ai, bi);
}
else
{
if(kind[bi]==kind[ai])
{
tag=1;
}
}
}
if(tag==0)
{
printf("Scenario #%d:\n", kk+1);
printf("No suspicious bugs found!\n\n");
}
else
{
printf("Scenario #%d:\n", kk+1);
printf("Suspicious bugs found!\n\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator