pku2492.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 68 行

#include <stdio.h>

typedef struct 
{
	int id, st;
}Node;

Node nd[2010];

int get_id(int x)
{
	int root;
	if (nd[x].id == 0)
	{
		return x;
	}
	root = get_id(nd[x].id);
	if (nd[x].id != root)
	{
		nd[x].st += nd[nd[x].id].st;
		nd[x].st %= 2;
		nd[x].id = root;
	}
	return root;
}

int main()
{
	int T, N, E, t, found;
	int i, j, s, e, hs, he;
	scanf("%d", &T);
	for (t = 0; t < T;)
	{
		scanf("%d%d", &N, &E);
		memset(nd, 0, sizeof(nd));
		found = 0;
		while (E--)
		{
			scanf("%d%d", &s, &e);
			if (found)
			{
				continue;
			}
			hs = get_id(s);
			he = get_id(e);
			if (hs != he)
			{
				nd[he].id = hs;
				nd[he].st = (nd[e].st + nd[s].st + 1) % 2;
			}
			else
			{
				if (nd[s].st == nd[e].st)
				{
					printf("Scenario #%d:\nSuspicious bugs found!\n\n", ++t);
					found = 1;
				}
			}
		}
		if (found == 0)
		{
			printf("Scenario #%d:\nNo suspicious bugs found!\n\n", ++t);
		}
	}
	return 0;
}