| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
无数次WA之后 果断BFS 水过 留码
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator