POJ 2492および調査セット
虫の性行為を調べて、まず虫に同性愛者がいないと仮定する.テストごとにN匹の虫を入力し、M個の数対(x,y)を入力し、x,yの間に性行為があることを示し、最後に仮説が成立したかどうかを判断する(すなわち同性愛があるかどうかを判断する).
#include <iostream>
using namespace std;
#define N 1000005
int opp[N], father[N], rank[N];
void make_set ( int x )
{
for ( int i = 0; i <= x; ++i )
{
father[i] = i;
opp[i] = rank[i] = 0;
}
}
int find_set ( int x )
{
if ( father[x] != x )
father[x] = find_set(father[x]);
return father[x];
}
void Union ( int x, int y )
{
int fx = find_set(x);
int fy = find_set(y);
if ( fx == fy ) return;
if ( rank[fx] > rank[fy] )
father[fy] = fx;
else
father[fx] = fy;
if ( rank[fx] == rank[fy] )
rank[fy]++;
}
int main()
{
int t, n, m, x, y;
bool find;
scanf("%d",&t);
for ( int i = 1; i <= t; ++i )
{
find = false;
scanf("%d%d",&n,&m);
make_set(n);
while ( m-- )
{
scanf("%d%d",&x,&y);
if ( find == false )
{
if ( opp[x] == 0 && opp[y] == 0 )
{
opp[x] = y;
opp[y] = x;
}
else if ( opp[x] != 0 && opp[y] == 0 )
{
opp[y] = x;
Union(y,opp[x]);
}
else if ( opp[x] == 0 && opp[y] != 0 )
{
opp[x] = y;
Union(x,opp[y]);
}
else if ( opp[x] != 0 && opp[y] != 0 )
{
if ( find_set(x) == find_set(y) )
find = true;
Union(x,opp[y]);
Union(y,opp[x]);
}
}
}
printf("Scenario #%d:
",i);
if ( find )
printf("Suspicious bugs found!
");
else
printf("No suspicious bugs found!
");
if ( i != t ) putchar('
');
}
return 0;
}