这个题目的写法有很多，用二分图染色也可以写，思路很好想，这里我们用关于并查集的两种写法来做。
题目大意：输入x,y表示x和y交配，然后判断是否有同性恋。
1 带权并查集：
我们可以用边的权值来表示一种关系，比如说
我们可以设权值为1，假如A和B发生关系，B和C发生关系，那么C到A的距离就是2，如果A和C发生关系，那就会产生矛盾，因此A和C是同性。
所以如果x和y可以发生关系，首先x和y必须在一棵树上，并且x和y到跟的距离必须同为奇数或者同为偶数。
code:
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=+;
int fa[N],w[N];
int find(int x){
if(x==fa[x]) return x;
else {
int c=find(fa[x]);
w[fa[x]]%=;
w[x]=(w[x]+w[fa[x]])%;
return fa[x]=c;
}
}
bool unite(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
fa[fx]=fy;
w[fx]=(w[y]-w[x]+)%;
return ;
}
else {
return w[x]%==w[y]%;
}
}
void solve(int time){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
fa[i]=i;
w[i]=;
}
int ans=;
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(ans) continue ;
if(unite(x,y)){
ans++;
// break;//注意这里不能直接break...wa了好几发，但是CF是可以的。。。
}
}
printf("Scenario #%d:\n",time);
if(ans) puts("Suspicious bugs found!\n");
else puts("No suspicious bugs found!\n");
}
int main(){
int t;cin>>t;
for(int i=;i<=t;i++) solve(i);
return ;
}
2 种类并查集：
如果用种类并查集来写，那这个题就相当于 食物链 那道题目的缩水版。。。
将每个元素分为两类，x和x+n，如果x和y可以发生关系，那么x和y不能是同类，也就是说x和y不能是一类,x+n和y+n不能是一类。
code:
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=+;
int fa[N+N];
int find(int x){
return fa[x]==x? x:fa[x]=find(fa[x]);
}
int unite(int x,int y){
int fx=find(x),fy=find(y);
fa[fx]=fy;
}
bool same(int x,int y){
return find(x)==find(y);
}
void solve(int time){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n+n;i++) fa[i]=i;
int ans=;
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
x--;y--;
if(ans) continue ;
if(same(x,y)||same(x+n,y+n)){
ans=;
// if(ans) break;//注意这里不能直接break...wa了好几发，但是CF是可以的。。。
}
else {
unite(x,y+n);unite(y,x+n);
}
}
printf("Scenario #%d:\n",time);
if(ans) puts("Suspicious bugs found!\n");
else puts("No suspicious bugs found!\n");
}
int main(){
int t;cin>>t;
for(int i=;i<=t;i++) solve(i);
return ;
}