我用BFS做的 WA了很久 今天都没有过！看看我那错了，很想知道，非常谢谢！
#include<iostream>
using namespace std;
int map[505][505],c[505][505];
int count[505][505];
bool visit[505];
bool f2[505][505];
int f[505];
bool bfs_adjust(int n,int u,int t)
{
	int i,j,front=0,rear=0;
	int que[1000];
	memset(visit,false,sizeof(visit));
	memset(f,-1,sizeof(f));
	que[rear++]=u;
	visit[u]=true;
	while(front<rear)
	{
		i=que[front++];
		for(j=0;j<n;j++)
		{
			if(!visit[j] && map[i][j] && !f2[i][j])
			{
				
				f[j]=i;
				visit[j]=true;
				que[rear++]=j;
				if(j==t)
					return true;
					
			}		  
		}
	}
	return false;
}
int main()
{
	int n,m,i,j,w,v;
	int a,b;
	bool flag,flag2;
	while(1)
	{
		scanf("%d %d",&n,&m);
		if(n==0 && m==0)
			break;
		flag2=flag=true;
		memset(count,0,sizeof(count));
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				map[i][j]=0;
			for(i=0;i<m;i++)
			{
				scanf("%d %d",&a,&b);
				map[a][b]=map[b][a]=1;
			}
			for(i=0;i<n;i++)
			{	
				for(j=0;j<n;j++)
				{	
					if(i!=j)
					{	
							memset(f2,false,sizeof(f2));
							 while(bfs_adjust(n,i,j))
								{   
								    count[i][j]++;
									if(count[i][j]>3)
										break;
									  v=j;
									  while(v>0)
									  {
										  w=f[v];
										  f2[w][v]=true;
										  f2[v][w]=true;
										  v=w;
									  }
							         
								}
							if(count[i][j]<3)
							{
								flag=false;
								flag2=false;
								break;
							}
                                					
					}
						
				}
				if(!flag2)
					break;
				
			}
			if(flag)
				printf("YES\n");
			else
				printf("NO\n");
			printf("\n");
	}
	return 0;
}

• 说说你的思路吧 (0) fuch 2008-12-28 17:30:49
  • Re:说说你的思路吧 (118) 200609020331 2008-12-28 20:48:26
    • Re:n*n*m的复杂度啊。不会超？ (122) xtu715 2008-12-28 21:13:08
      • Re:n*n*m的复杂度啊。不会超？ (9) 200609020331 2008-12-28 21:21:59
      • Re:n*n*m的复杂度啊。不会超？ (147) skyfly 2008-12-29 16:35:53
        • Re:n*n*m的复杂度啊。不会超？ (155) 200609020331 2008-12-29 21:28:33
    • Re:说说你的思路吧 (167) Etfl 2010-06-14 12:32:17