文章目录

• 一、并查集Disjoint Set？
• 二、代码

---

一、并查集Disjoint Set？

主要是判断图中是否出现了环。

二、代码

#include<bits/stdc++.h>
using namespace std;
int VERTICES = 6;
void initialise(int parent[],int rank[]) { //赋初值
	for(int i=0;i<VERTICES;i++) {
		parent[i] = -1;
		rank[i] = 0;
	}
}

int find_root(int x,int parent[]) { //查找根节点 
	int x_root = x;
	while(parent[x_root] != -1) {
		x_root = parent[x_root];
	}
	return x_root;
} 

int union_vertices(int x,int y,int parent[],int rank[]) {  //联结 
	int x_root = find_root(x,parent);
	int y_root = find_root(y,parent);
	if(x_root == y_root) {
		return 0;
	}
	else {   //尽可能把矮的树连接到高的树上
		if(rank[x_root] > rank[y_root]) {
			parent[y_root] = x_root;
		}
		else if(rank [y_root] > rank[x_root]) {
			parent[x_root] = y_root;
		}
		else {  //树高相同，随便连接
			parent[x_root] = y_root;
			rank[y_root]++;
//			cout<<"#"<<endl;
		}
		return 1;
	}
}

signed main() {
	int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5}};
	int parent[6]= {0};
	int rank[6] = {0};
	memset(parent,-1,sizeof(parent));
	memset(rank,0,sizeof(rank));
	initialise(parent,rank);//赋初值
	for(int i = 0;i<6;i++) {  //遍历每条边
		int x = edges[i][0];
		int y = edges[i][1];
		if(union_vertices(x,y,parent,rank) == 0) {
			cout<<"有环"<<endl;
			exit(0);
		}
	}
//	for(auto j : rank) {
//		cout<<j<<endl;
//	}
	cout<<"无环"<<endl;
	return 0;
}