染色那种做法.不会写并查集,会的人愿意指导一下吗?
#include <stdio.h>
#include <string.h>
const int maxn = 2000+5;
int n,m,mat[maxn][maxn],flag[maxn];
bool ok;

void paint(int a)
{
	int i;
	for (i=1;i<=n;i++)
	{
		if (mat[a][i]==1)
		{
			if (flag[i]==0)
			{
				if (flag[a]==1){
					flag[i]=2;
					paint(i);
				}
				else {
					flag[i]=1;
					paint(i);
				}
			}
			else
			{
				if (flag[a]==flag[i]) {
					 ok = false;
					 return;
				}
				else continue;
			}
		}
	}
}

int main()
{
	int cases,a,b,c = 0,i;

	scanf("%d",&cases);
	while (cases --)
	{
		c ++;
		scanf("%d %d",&n,&m);
		memset(mat,0,sizeof(mat));
		for (i = 0 ; i < m;i ++)
		{
			scanf("%d %d",&a,&b);
			mat[a][b]=mat[b][a]=1;
		}
		memset(flag,0,sizeof(flag));
		ok = true;
		for (i=0;i<=n;i++)
		{
			if (flag[i]==0)
			{
				flag[i]=1;
				paint(i);
			}
		}
		printf("Scenario #%d:\n",c);
		if (ok)
			printf("No suspicious bugs found!\n\n");
		else
			printf("Suspicious bugs found!\n\n");
	}
	return 0;
}

• 好像很多重复递归，加些剪枝，或者干脆开队列，广搜 (1176) sunmoonstar_love 2005-08-09 16:37:10
  • 广搜,加了点STL,更慢了:( 我拿标称交了一次.比自己写的还慢.我的广搜版本比深搜还慢.请教一下并查集怎么做 (0) bakey 2005-08-09 17:14:45
• 还是用并查集吧，每个点有个父节点。通过合并树来合并集合。具体可以去网上搜一下 (1176) tengshengbo 2005-08-09 17:17:15