A Bug‘s Life
Input
Output
Sample Input
2 3 3 1 2 2 3 1 3 4 2 1 2 3 4
Sample Output
Scenario #1: Suspicious bugs found! Scenario #2: No suspicious bugs found!
题意：给出n条昆虫，m对关系。给出a,b表示a与b属于异性。问是否出现了同性恋昆虫。
解析：
解法一：跟之前的POJ1703一个解法，对称一下，a,b为异性，那么a+n,b为同性 a,b+n为同性。每次判断一下即可。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e4; bool vis[maxn]; int pr[maxn]; int n,m; int find(int x) { if(x!=pr[x]) pr[x]=find(pr[x]); return pr[x]; } void join(int x,int y) { int f1=find(x); int f2=find(y); if(f1!=f2) { pr[f1]=f2; } return ; } void init() { for(int i=1;i<=2*n+100;i++) pr[i]=i; } bool check(int x,int y) { if(find(x)!=find(y)) return false; return true; } int main() { int t; scanf("%d",&t); int ac=1; while(t--) { scanf("%d%d",&n,&m); int ok=0; init(); while(m--) { int x,y; scanf("%d%d",&x,&y); join(x+n,y); join(x,y+n); if(check(x,y)||check(x+n,y+n)) { ok=1; } } // for(int i=1;i<=2*n;i++) // cout<<pr[i]<<" "; // cout<<endl; printf("Scenario #%d:\n",ac++); if(ok) cout<<"Suspicious bugs found!"<<endl; else cout<<"No suspicious bugs found!"<<endl; cout<<endl; } }
解法二：用带权并查集的方式做。加入vis[]来描述性别异同，这里统一为0，1两个数字。vis[i]==0表示i与它的根节点为同性，==1为异性。即vis[]描述的是当前昆虫与它的根节点的性别异同关系。find()和join()函数就必须做出改变了，find里面必须要有路径压缩。即：
先说find()，找C节点的父亲节点，pr[C]=B，会先找到B，而vis[C]记录的是C与B的异同关系，所以到最终的父亲节点就不是这个vis[C]了，所以我们要更新vis[C]。即为vis[C]=(vis[C]+vis[pr[C]])%2了。这个可以自己设个样例找一下，的确是这个公式将vis[C]指向了A节点。随着父亲节点不停的改变，中途的vis[]也是随着变动。
if(x!=pr[x]) { int father=find(pr[x]); vis[x]=(vis[x]+vis[pr[x]])%2; pr[x]=father; } return pr[x];
再说join()，1：进入的a,b如果根节点相同，那么直接判断它们的vis[]是否相同，相同即为同性恋，否则不是。2：a,b的根节点不同，那么就将a,b所属的两棵树连接起来。这个时候是默认a,b的确如输入所表达的意思：异性。那么a,b的根节点的链接，需要建立起联系，需要由vis[a]和vis[b]来建立。公式就是：vis[father(a)]=(vis[a]+vis[b]+1)%2; 这样father(a)和father(b)的性别异同关系就建立起来了。
总的来讲，这个解法，每次是先判断，再执行操作的，发现同性恋，就不进行操作了。否则就默认正常，再操作下去。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=2e3+10; int pr[maxn],vis[maxn]; int n,m; void init() { for(int i=1;i<=n;i++) { pr[i]=i; vis[i]=0; } } int find(int x) { if(x!=pr[x]) { int father=find(pr[x]); vis[x]=(vis[x]+vis[pr[x]])%2; pr[x]=father; } return pr[x]; } int join(int x,int y) { int f1=find(x),f2=find(y); if(f1==f2) { if((vis[x]+vis[y])%2==0) return 1; else return 0; } else { pr[f1]=f2; vis[f1]=(vis[x]+vis[y]+1)%2; } return 0; } int main() { int t; scanf("%d",&t); int ac=1; while(t--) { scanf("%d%d",&n,&m); init(); int ok=0; while(m--) { int a,b; scanf("%d%d",&a,&b); if(join(a,b)==1) { ok=1; } } printf("Scenario #%d:\n",ac++); if(ok) { cout<<"Suspicious bugs found!"<<endl; } else { cout<<"No suspicious bugs found!"<<endl; } cout<<endl; } }
原文：https://www.cnblogs.com/liyexin/p/12602131.html