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;
}