> 染色那种做法.不会写并查集,会的人愿意指导一下吗?
> #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;
> }

• 广搜,加了点STL,更慢了:( 我拿标称交了一次.比自己写的还慢.我的广搜版本比深搜还慢.请教一下并查集怎么做 (0) bakey 2005-08-09 17:14:45