C/C++ | 并查集：用于检查一个图上有没有环

 没有环的过程分析： 

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define VERTICES 6
#define LINE 5
using namespace std;

/*
	parent:数组解决并查集合并问题
	VERTICES:设定的顶点数
	LINE:设定的边数
*/
void initialise(int *parent)
{
	//用于parent数组的初始化
	int i;
	for(i=0;i<VERTICES;i++)
	{
		parent[i]=-1;
	 }
}
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[])
{
	//用于合并两个集合 。返回0：合并成功，返回1：合并失败
	int x_root=find_root(x,parent);
	int y_root=find_root(y,parent);
	printf("x:当前数是%d,他的parent是：%d\n",x,x_root);
	printf("y:当前数是%d,他的parent是：%d\n",y,y_root);

	if(x_root==y_root)
	{
		return 0;
	}
	else
	{
		parent[x_root]=y_root;//将x连到y上
		return 1;
	}

}
int main()
{
	int parent[VERTICES]={0};
	initialise(parent);
	int edges[LINE][2] = {
			{0,1},{1,2},{1,3},
	    	{2,4},{2,5}
		};
	for(int i=0;i<LINE;++i)
	{
		int x=edges[i][0];
		int y=edges[i][1];
		if(union_vertices(x,y,parent)==0)
		{
			printf("存在环");
			exit(0);
		}
	}
	printf("没有环");
	return 0;
 } 

存在环的过程分析：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define VERTICES 6
#define LINE 6
using namespace std;

/*
	parent:数组解决并查集合并问题
	VERTICES:设定的顶点数
	LINE:设定的边数
*/
void initialise(int *parent)
{
	//用于parent数组的初始化
	int i;
	for(i=0;i<VERTICES;i++)
	{
		parent[i]=-1;
	 }
}
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[])
{
	//用于合并两个集合 。返回0：合并成功，返回1：合并失败
	int x_root=find_root(x,parent);
	int y_root=find_root(y,parent);
	printf("x:当前数是%d,他的parent是：%d\n",x,x_root);
	printf("y:当前数是%d,他的parent是：%d\n",y,y_root);

	if(x_root==y_root)
	{
		return 0;
	}
	else
	{
		parent[x_root]=y_root;//将x连到y上
		return 1;
	}

}
int main()
{
	int parent[VERTICES]={0};
	initialise(parent);
	int edges[LINE][2] = {
			{0,1},{1,2},{1,3},
	    	{2,4},{2,5},{3,4}
		};
	for(int i=0;i<LINE;++i)
	{
		int x=edges[i][0];
		int y=edges[i][1];
		if(union_vertices(x,y,parent)==0)
		{
			printf("存在环");
			exit(0);
		}
	}
	printf("没有环");
	return 0;
 }