地址: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; }