本文共 879 字，大约阅读时间需要 2 分钟。

并查集的最大作用是检测一个图上面存不存在环。

#include
   
    #include
    
     #define  VERTICES 6void initialise(int parent[]){
   	int i;	for(i=0;i
    
   

进行优化后：

#include
   
    #include
    
     #define  VERTICES 6void initialise(int parent[],int rank[]) {
   	int i;	for(i=0; i
     
      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]++;		}		return 1;	}}int main(void) {
   	int parent[VERTICES]= {
   0};	int rank[VERTICES]= {
   0};	int edges[6][2]= {
   		{
   0,1},{
   1,2},{
   1,3},{
   2,4},{
   3,4},{
   2,5}	};	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)) {
   			printf("Cycle detected!\n");			exit(0);		}	}	printf("no cycle found.\n");	return 0;}
     
    
   

转载地址：http://seawi.baihongyu.com/