并查集--简单记录

骑猪看日落 2023-01-22 10:58 16阅读 0赞

并查集也是一种树状结构，用于处理一些不相交集合的合并以及查询问题

查询：

int find(int x)
    { 
    	while(x!=parent[x]) x = parent[x];
    	return x;
    }

这种方法递归耗时多，且有大量的重复计算。

稍微改变一下：

int find(int x)
    { 
    	while(x!=parent[x])
    	return x = parent[x];
    }

根据递归的性质，把节点直接全部连接到根节点上

如果数据很大，递归可能会溢出栈

int find(int x)
    { 
    	int y = x;
    	while(y!=parent[y])
    	{ 	
    		y = parent[y];
    	}
    	while(x!=parent[x])
    	{ 
    		int px = parent[x];
    		parent[x] = y;
    		x = px;
    	}
    	return y;
    }

上述过程规避了回溯过程中返回值的问题，先找到父亲节点，再沿着路径一一修改。  
合并操作：

void Union(int a, int b)
    { 
    	parent[b] = a;
    }

例题：  
[http://acm.hdu.edu.cn/showproblem.php?pid=1232][http_acm.hdu.edu.cn_showproblem.php_pid_1232]

两个城市有路证明在同一个集合中，换句话说，a城市和b城市相连，则可以将a所在的集合和b所在的集合合并成一个集合，一个集合内任意两个城市都是相连的  
最后，看有多少个**集合数**，只要把这些集合连接起来就可以

#include<bits/stdc++.h>
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    using namespace std;
    
    int pre[1005];  
    
    int finds(int x)
    { 
    	while(x==pre[x]) // 初始条件下的父亲节点
    	{ 
    		return x;
    	}
    	return x=finds(pre[x]); // return finds(pre[x]);
    }
    
    void unions(int x,int y)
    { 
        int x1=finds(x); // 找到x1的父亲节点
        int x2=finds(y); // 找到x2的父亲节点
        if(x1!=x2) // 指向同一个父亲节点
        { 
            pre[x1]=x2;
        }
    }
    
    void solve()
    { 
    	int n, m;
    	while(scanf("%d%d",&n,&m))
    	{ 
    	    if (n==0) break;
    		rep(i,1,n) pre[i] = i;
    		while(m--)
    		{ 
    			int a,b;
    			scanf("%d%d",&a,&b);
    			unions(a,b);
    		}
    		int ans = 0;
    		rep(i,1,n)
    			if(pre[i]==i) ans++;
    
    		cout << ans-1 << endl; //减一的原因是：减掉自身的那个集合
    	}	
    }
    
    int main()
    { 
        solve();
        return 0;
    }

//代码二
    #include<bits/stdc++.h>
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    using namespace std;
    
    int pre[1005];  
    
    int finds(int x)
    { 
    	int y = x;
    	while (y!=pre[x])
    	{ 
    		y=pre[y];
    	}
    	while(x!=pre[x]) 
    	{ 
    		int px = pre[x];
    		pre[x]=y;
    		x=px;
    	}
    	return y;
    }
    
    void Union(int a, int b)
    { 
    	pre[a] = b;
    }
    
    void solve()
    { 
    	int n, m;
    	while(scanf("%d%d",&n, &m) && n!=0)
    	{ 
    		rep(i,1,n) pre[i] = i;
    		while(m--){ 
    			int a, b;
    			scanf("%d%d",&a, &b);
    			if(finds(a)!=finds(b)){ 
    				Union(finds(a), finds(b));
    			}
    		}
    		int ans = 0;
    		rep(i,1,n) if(pre[i]==i) ans++;
    		cout << ans-1<< endl;
    	}
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr); cout.tie(nullptr);
        // int T; cin >> T;
        // while (T--)
            solve();
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1232]: http://acm.hdu.edu.cn/showproblem.php?pid=1232