| ||||||||||
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