学步园

题目: http://poj.org/problem?id=2492

每个人不是"男"就是"女"。每个人就是一对点集a,a'。 判断是否有同性恋，就是2-sat判定 抄poj3678啦啦啦

//2-sat
//适用于点集成对给出，最多只能取其中一个。
//poj3678
//建图: 0..n-1取0; n..2n-1取1
//连接某边是为了推出矛盾。x->y表示选x则必须选y
//求一次极大连通子图，判断id[i]==id[i+n]这个矛盾是否成立既可。
#include <string.h>
#include <stdio.h>
#define MAXN 4100
int find_components(int n,bool mat[][MAXN],int* id){
	int ret=0,a[MAXN],b[MAXN],c[MAXN],d[MAXN],i,j,k,t;
	for (k=0;k<n;id[k++]=0);
	for (k=0;k<n;k++)
		if (!id[k]){
			for (i=0;i<n;i++)
				a[i]=b[i]=c[i]=d[i]=0;
			a[k]=b[k]=1;
			for (t=1;t;)
				for (t=i=0;i<n;i++){
					if (a[i]&&!c[i])
						for (c[i]=t=1,j=0;j<n;j++)
							if (mat[i][j]&&!a[j])
								a[j]=1;
					if (b[i]&&!d[i])
						for (d[i]=t=1,j=0;j<n;j++)
							if (mat[j][i]&&!b[j])
								b[j]=1;
				}
			for (ret++,i=0;i<n;i++)
				if (a[i]&b[i])
					id[i]=ret;
		}
	return ret;
}
int id[MAXN];
bool mat[MAXN][MAXN];

int main(){
    int n,m,i,j,k,x,y,a,b,c,T,cases;
    char op[8];
    scanf("%d",&T);
    for (cases=1;cases<=T;cases++)
{

    scanf("%d %d",&n,&m);
    memset(mat,0,sizeof(mat));
    memset(id,0,sizeof(id));
    for (i=0;i<m;i++){
        scanf("%d %d",&a,&b);
        a--;b--;
        mat[a][b+n]=mat[b][a+n]=mat[a+n][b]=mat[b+n][a]=1;
    }
    find_components(2*n,mat,id);
    int ans=1;
    for (i=0;i<n;i++){
        if (id[i]==id[i+n]) ans=0;
//        printf("node=%d id=%d  node'=%d id=%d\n",i,id[i],i+n,id[i+n]);
    }
    printf("Scenario #%d:\n",cases);
    if (ans==1) printf("No suspicious bugs found!\n\n");else printf("Suspicious bugs found!\n\n");
}

    return 0;
}