我是一个个的搜的//////

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int bug[2010], mark[2010][2010], ii[2010], use[2010];   //   bug[i]记录虫i的性别（0为没记录），mark[i]记录与虫i有关系的虫一个个放入
                                                        //  ii[k] 记录与k虫有关系的虫个数，use记录该虫是否搜过

bool find(int k)
{
	int i,s = 1;
	if(bug[k] == 1)              // 要与K不同的性别
		s = 2;	
	for(i=0; i<ii[k]; i++)
	{
		if(bug[ mark[k][i] ] == bug[k])
			return true;
		else if(use[ mark[k][i] ]==0)
		{
			bug[ mark[k][i] ] = s;
			use[ mark[k][i] ] = 1;
			if(find(mark[k][i]))
				return true;
		}
	}
	return false;
}



int main()
{
	int i,t,n,m,a,b,sig,k=1;
	scanf("%d", &t);
	while(t--)
	{
		memset(bug, 0, sizeof(bug));
		memset(mark, 0, sizeof(mark));
		memset(ii, 0, sizeof(ii));
		memset(use, 0, sizeof(use));
		scanf("%d%d", &n, &m);
		for(i=0; i<m; i++)
		{
			cin>>a>>b;
			mark[a][ii[a]++] = b;
			mark[b][ii[b]++] = a;
		}
		sig = 0;
		for(i=1; i<=n; i++)
		{
			if(!use[i] && ii[i] != 0)
			{
				bug[i] = 1;
				use[i] = 1;  
				if(find(i))
				{
					sig = 1;
					break;
				}
			}
		}
		printf("Scenario #%d:\n", k);
		k += 1;
		if(sig)
			printf("Suspicious bugs found!\n\n");
		else
			printf("No suspicious bugs found!\n\n");
	}
	return 0;
}

• 燕过留声：并查集 (0) pku_admin 2010-03-16 21:41:50
• 慢死了还比我快 (1467) wyu_Onway 2010-04-14 23:11:00