手残残一题，脑残毁一生系列~~
明明跟POJ 1703是一样的思路啊呀喂，昨天晚上调到死也调不出来啊呀喂~~
今早晨才发现初始化函数放错位置了~~
不能再这样了啊~~
题目大意：
有N个虫子，只有异性交配才是正常的，但我们不知道哪个虫子的性别是什么。给出M个交配事件，问能否发现同性交配的事件。
解题思路：
跟1703一样，种类并查集。只不过上一次是帮派，这一次是性别~
下面是代码：
#include <stdio.h> int n,q; int fath[2005],a[2005]; void init() { for(int i=1; i<=n; i++) { fath[i]=i; a[i]=0; } } int findd(int x) { if(x==fath[x])return x; int y=findd(fath[x]); a[x]=(a[x]+a[fath[x]])&1; fath[x]=y; return y; } bool SetUnion(int x,int y) { int fx=findd(x); int fy=findd(y); if(fx==fy) { if(a[x]==a[y])return true; else return false; } fath[fx]=fy; if(a[y]) { a[fx]=a[x]; } else { a[fx]=1-a[x]; } return false; } int main() { int t,case1=1,x,y; scanf("%d",&t); while(t--) { bool flat=true; scanf("%d%d",&n,&q); init(); for(int i=0; i<q; i++) { scanf("%d%d",&x,&y); if(SetUnion(x,y))flat=false; } printf("Scenario #%d:\n",case1++); if(!flat)puts("Suspicious bugs found!\n"); else puts("No suspicious bugs found!\n"); } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996670.html
相关资源：JAVA上百实例源码以及开源项目