poj1741，poj 2492

地址：http://poj.org/problem?id=2492

題意：判斷是否有同性戀。。。

poj1741。mark：解題報告主流思想是并查集，我用的bfs。

　　　wa了很多次，都是一些不細心。而且這題居然每組數據后面都有一個空格。。。。

代碼：

#include <stdio.h>
#include <queue>
#include <string.h>using namespace std;bool a[2010][2010];
int b[2010];
int f[2010];
int m;int pd()
{int fr,la,i,j,p;queue<int> q;for(i = 1; i <= m; i++){if(b[i] == -1){b[i] = 0;q.push(i);f[i] = 1;while(!q.empty()){p = q.front();q.pop();for(j = 1; j <= m; j++)if(a[p][j]){if(b[j] == b[p]) return 0;b[j] = 1-b[p];if(!f[j]) {f[j] = 1; q.push(j);}}}}}return 1;
}int main()
{int t,n,p,q;int i,j,k;scanf("%d", &t);for(k = 0; k < t; k++){scanf("%d%d", &m, &n);memset(a, 0, sizeof(a));memset(b, -1, sizeof(b));memset(f, 0, sizeof(f));for(i = 0; i < n; i++){scanf("%d%d", &p, &q);a[p][q] = 1;a[q][p] = 1;}printf("Scenario #%d:\n", k+1);puts(pd() ? "No suspicious bugs found!\n" : "Suspicious bugs found!\n");}return 0;
}