Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

无数次WA之后 果断BFS 水过 留码

Posted by zihuacs at 2010-08-06 17:02:10 on Problem 2492
#include<iostream>
#include<queue>
using namespace std;
bool map[2000][2000];
int color[2000];
int n,m;
bool ans;

void BFS(int t)
{
	int k,i;
	ans=true;
	queue<int> qu;
	qu.push(t);
	while(!qu.empty())
	{
		k=qu.front();
		qu.pop();
		for(i=0; i<n; i++)
		{
			if(map[i][k]==true)
			{
				if(color[k]==color[i])
				{
					ans=false;
					return;
				}
				if(color[i]==-1)
				{
					color[i]=(color[k]+1)%2;
					qu.push(i);
				}
			}
		}
	}
}
int main(void)
{
	int test_num,test_case;
	int i,j;
	int r1,r2;
	scanf("%d",&test_num);
	for(test_case=1; test_case<test_num+1; test_case++)
	{
		scanf("%d %d",&n,&m);
		for(i=0; i<n; i++)
		{
			color[i]=-1;
			for(j=0; j<n; j++)
			{
				map[i][j]=false;
			}
		}
		for(i=0; i<m; i++)
		{
			scanf("%d %d",&r1,&r2);
			map[r1-1][r2-1]=true;
			map[r2-1][r1-1]=true;
		}
		ans=true;
		for(i=0; i<n && ans; i++)
		{
			if(color[i]==-1)
			{
				color[i]=0;  //  
				BFS(i);
			}
		}
		printf("Scenario #%d:\n",test_case);
		if(ans)
		{
			printf("No suspicious bugs found!\n\n");
		}
		else
		{
			printf("Suspicious bugs found!\n\n");
		}
	}
	system("pause");
	return 0;
}
/*
4 4
1 2
2 3
3 4
3 1
*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator