【算法与数据结构】——并查集

并查集
【算法与数据结构】——并查集
【算法与数据结构】—— 并查集
两位大佬写的太好了,现在加入了一些自己的理解，进行简化。

侵删。

void init(int n)     				//并查集的初始化
{
    for(int i = 0; i < n; i++){
        pre[i] = i;     			//每个结点的上级都是自己 
    } 
}
int find(int x)					//查找x的代表元
{
	//找这个树的根节点(即"教主"),根节点(即"教主")的特点是:"他的上级是他自己"!
	while(pre[x] != x)			//如果x的前驱结点不是自己,就一直找,目的是:找到根节点(即"教主")
		x = pre[x];
	return x;               //找到"教主"后,返回"教主"
}
void join(int x,int y)    // 将两个集合合并                
{
    int fx=find(x), fy=find(y); 
    if(fx != fy) 
        pre[fx]=fy;	//fy做fx的前驱结点
}

find()函数优化:优化后的特点是 : =>将 可能的 “单支树结构(一字长蛇形)” 修改为 “N叉树”,
即再次遍历时,不用再遍历那么多,只需要遍历一次,即可遍历到他的最终大BOSS(也叫教主,也叫根节点)
即:第一次执行查找 *** 作的时候是实现没有压缩效果的，只有在之后才有效。

void init(int n)     				//并查集的初始化
{
    for(int i = 0; i < n; i++){
        pre[i] = i;     			//每个结点的上级都是自己 
    } 
}
int find(int x)     				//查找结点 x的根结点 
{
    if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点        
    return pre[x] = find(pre[x]);	//此代码相当于先找到根结点 rootx，然后pre[x]=rootx 
}
void join(int x,int y)    // 将两个集合合并                
{
    int fx=find(x), fy=find(y); 
    if(fx != fy) 
        pre[fx]=fy;	//fy做fx的前驱结点
}

用一道力扣的题来巩固入门
547. 省份数量
题解

模板
先默写初始化init()函数,find()函数,join()函数;
然后再主要实现功能的函数findCircleNum()中,
先初始化 比如说: 1->1 2->2 3->3…;
再合并 比如说: 1->2->3 2->4 5->5 6->6…;
再用find()函数,将一字长蛇阵,转成N叉树; 1->2,1->3,1->4,5->5,6->6 (可以理解为:老板->员工)
最后用set去重;(最终pre中放的都是老板,用set去重,得到有几个老板,也就是说几个省份)

class Solution {
public:
    int pre[200];//放省份,最多为y个
    void init(int n)     				//并查集的初始化
    {
        for(int i = 0; i < n; i++){
            pre[i] = i;     			//每个结点的上级都是自己 
        } 
    }
    int find(int x)     				//查找结点 x的根结点 
    {
        if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点        
        return pre[x] = find(pre[x]);	//此代码相当于先找到根结点 rootx，然后pre[x]=rootx 
    }
    void join(int x,int y)    // 将两个集合合并                
    {
        int fx=find(x), fy=find(y); 
        if(fx != fy) 
            pre[fx]=fy;	//fy做fx的前驱结点
    }

    
    int findCircleNum(vector<vector<int>>& isConnected) {
        int cnt = 0;
        int y = isConnected.size();
        int x = isConnected[0].size();
        init(y);//初始化

        for(int i = 0 ; i< y;i++){//合并
            for(int j = 0 ; j< x ;j++){
                if(isConnected[i][j]==1){
                     join(i,j);//如果是同一省份,就合并
                }
            }
        }
        for(int i = 0 ; i< y;i++){//再将一字长蛇阵变成N叉树,
        //即,每个人的上级要么是一个人(最终大BOSS),要么是自己
                find(i);
        }
        unordered_set<int>s;
        for(int i = 0;i<y;i++){//一个老板对应多个员工,将老板去重
            cout<<pre[i]<<" ";
            s.insert(pre[i]);
        }
        return s.size();//最终返回有几个老板
    }
};

再来一个题吧!!!
128. 最长连续序列

class Solution {
public:

	map<int,int>pre;
	void init(int n,vector<int>& v)     				//并查集的初始化
	{
    	for(int i = 0; i < n; i++){
       	 pre[v[i]] = v[i];     			//每个结点的上级都是自己 
    	} 
	}
	int find(int x)					//查找x的代表元
	{
		//找这个树的根节点(即"教主"),根节点(即"教主")的特点是:"他的上级是他自己"!
		while(pre[x] != x)			//如果x的前驱结点不是自己,就一直找,目的是:找到根节点(即"教主")
			x = pre[x];
		return x;               //找到"教主"后,返回"教主"
	}
	void join(int x,int y)    // 将两个集合合并                
	{
  	  int fx=find(x), fy=find(y); 
   	 	if(fx != fy) 
    	    pre[fx]=fy;	//fy做fx的前驱结点
	}

    int longestConsecutive(vector<int>& nums) {
        int n =nums.size();
        if(n==0)return 0;
        if(n==1)return 1;

        //接下来,nums至少有两个数
        set<int>s;//对nums去重,再顺便对set进行排序
        for(int i = 0;i<n;i++){
            s.insert(nums[i]);
        }
        vector<int>v;
        for(auto it=s.begin();it!=s.end();it++){
            v.push_back(*it);
        }
        int n1=v.size();
        cout<<"n"<<n<<";n1:"<<n1<<endl;
        init(n1,v);
        //调试代码
        /*for(int i = 0 ; i< n1;i++){/
                cout<"<
        for(int i = 0;i<n1-1;i++){
            if(v[i+1]==v[i]+1){//后边的数比前面的数大1
                join(v[i+1],v[i]);
            }
        }
        //调试代码
        /*for(int i = 0 ; i< n1;i++){/
                cout<"<
				
        for(int i = 0 ; i< n1;i++){//再将一字长蛇阵变成N叉树,
        //即,每个人的上级要么是一个人(最终大BOSS),要么是自己
                find(v[i]);
        }
				
			  //调试代码
        /*for(int i = 0 ; i< n1;i++){//再将一字长蛇阵变成N叉树,
        //即,每个人的上级要么是一个人(最终大BOSS),要么是自己
                cout<

        //判断好是统计员工还是老板,如果只统计老板,那最后就用set去重,
        //如果统计的是:每家公司中,员工和老板人数的总和,那就不用set,直接统计重复数字的个数就行
        int max=0;
        map<int,int>cnt;
        for(int i = 0 ; i< n1;i++){//再将一字长蛇阵变成N叉树,
        //即,每个人的上级要么是一个人(最终大BOSS),要么是自己    
                cnt[pre[v[i]]]++;
                if(cnt[pre[v[i]]]>max)max=cnt[pre[v[i]]];
        }

        return max;
    }
};