并查集disjoinset union

并查集

并查集就是判断一个图是不是存在环
观看正月点灯笼的视屏


并查集最大的作用就是检查一个图中是否存在环

#include <iostream>
// 并查集
using namespace std;
void init(int parent[])// 初始化 每个点的的父亲都是-1
{
    int i;
    for(i=0; i<10; i++)
        parent[i]=-1;
}
// 查找每个点的根节点
// 并且判断是不是-1，知道找到最终的根节点 返回  x_root
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_ver(int x,int y,int parent[])
{
    int x_root=find_root(x,parent);
    int y_root=find_root(y,parent);
    if(x_root==y_root) {
        return 0;
    } else {
        parent[x_root]=y_root;
        return 1;
    }
}
int main()
{
    int parent[99]= {0};
    int array[5][2]= {{0,1},{1,2},{1,3},{3,4},{2,5}};
    init(parent);
    int flag=0;
     int i;
    for(i=0; i<5; i++) {
        int x=array[i][0];
        int y=array[i][1];
        if(union_ver(x,y,parent)==0) { // 判断图是否有环
            cout<<"Yes 环"<<endl;
            flag=1;
            break;
        }
    }
    
    if(flag==0)
        cout<<"No 环"<<endl;
    return 0;
}

算法优化：：
解决代码处理数据过多，导致复杂度为O(n)的问题

#include <iostream>
// 并查集
using namespace std;
void init(int parent[],int brank[])
{
    int i;
    for(i=0; i<10; i++) {
        parent[i]=-1;
        brank[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_ver(int x,int y,int parent[],int brank[])
{
    int x_root=find_root(x,parent);
    int y_root=find_root(y,parent);
    if(x_root==y_root) {
        return 0;
    } else {
        if(brank[x_root]>brank[y_root])
        {
        	parent[y_root]=x_root;
		}
		else if( brank[y_root]>brank[x_root])
		{
			parent[x_root]=y_root; 
		}
		else
		{
			parent[x_root]=y_root;
			brank[x_root]++;
		}
        return 1;
    }
}
int main()
{
    int parent[99]= {0};
    int brank[99]= {0};
    int array[5][2]= {{0,1},{1,2},{1,3},{3,4},{2,5}};
    init(parent,brank);
    int flag=0;
    int i;
    for(i=0; i<5; i++) {
        int x=array[i][0];
        int y=array[i][1];
        if(union_ver(x,y,parent,brank)==0) {
            cout<<"Yes row"<<endl;
            flag=1;
            break;
        }
    }

    if(flag==0)
        cout<<"No row"<<endl;
    return 0;
}

优化核心代码：：

// 加入brankz数组 判断 那个节点该往哪个方向结，谁作为根节点，让计算机，计算的次数更少。
// 将brank 度深的作为根节点，再并上其他集合，度深不变，
度相同的话，随便选择一共作为根节点，根节点度增加1；
if(brank[x_root]>brank[y_root])
        {
        	parent[y_root]=x_root;
		}
		else if( brank[y_root]>brank[x_root])
		{
			parent[x_root]=y_root; 
		}
		else
		{
			parent[x_root]=y_root;
			brank[x_root]++;
		}

ok 加油！！1