HDU - 1829 A Bug's Life （並查集應用）

題意：判斷有沒有同性戀的一道題，其實也可以看成是：在一顆二叉樹上是否有環

思路：在並查集的基礎上，有區別的一步是：當是新的兩個樹合並的時候，除了將一個根設為另一顆樹的根的父親外，還要加上不同性別的一層關系，我們開新的數組，vis[i]=j表示i和j是異性，還要的是將i的根的異性伙伴與j的根合並

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 1000005;
const int INF = 10000000;

int fa[MAXN];
int vis[MAXN];
int flag,n,m;

int find(int x){
	if (x != fa[x])
		fa[x] = find(fa[x]);
	return fa[x];
}

void Union(int x,int y){
	int fx = find(x),fy = find(y);
	if (fx == fy)
		flag = 0;
	else {
		if (vis[fx])
			fa[vis[fx]] = fy;
		if (vis[fy])
			fa[vis[fy]] = fx;
		vis[fx] = fy,vis[fy] = fx;
	}
}

int main(){
	int t,cas=1;;
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&n,&m);
		flag = 1;
		for (int i = 0; i <= n; i++)
			fa[i] = i,vis[i] = 0;
		for (int i = 0; i < m; i++){
			int a,b;
			scanf("%d%d",&a,&b);
			Union(a,b);
		}
		printf("Scenario #%d:\n",cas++);
		if (flag)
			printf("No suspicious bugs found!\n\n");
		else printf("Suspicious bugs found!\n\n");
	}
	return 0;
}