ACM模板——并查集

#define _for(i,a,b) for(int i = (a);i < (b);i ++) const int maxn = 50003; int par[maxn]; //父亲 int high[maxn]; //树的高度void init(int n) {_for(i,0,n){par[i] = i;high[i] = 0;} } int find(int x) {return par[x] == x ? x : par[x] = find(par[x]); }void unite(int x,int y) {x = find(x);y = find(y);if(x==y) return ;if(high[x]<high[y])par[x] = y;else{par[y] = x;if(high[x]==high[y])high[x] ++;} }bool same(int x,int y) {return find(x) == find(y); } 路径压缩普通并查集

 

#define _for(i,a,b) for(int i = (a);i < (b);i ++) const int maxn = 50003; int par[maxn]; //父亲 void init(int n) {_for(i,0,n)par[i] = i; } int find(int x) {return par[x] == x ? x : find(par[x]); }void unite(int x,int y) {x = find(x);y = find(y);if(x==y) return ; par[x] = y; }bool same(int x,int y) {return find(x) == find(y); } 朴实无华的并查集

 

#include <bits/stdc++.h> using namespace std;#define _for(i,a,b) for(int i = (a);i < (b);i ++) const int maxn = 50003; int par[maxn]; //父亲 int high[maxn]; //树的高度 int id[maxn]; //映射，里面装的是现在真正的序号 int idEnd; void init(int n) {idEnd = n;_for(i,0,n){par[i] = id[i] = i;high[i] = 0;} } int find(int x) {return par[x] == x ? x : par[x] = find(par[x]); }void unite(int x,int y) {x = find(x);y = find(y);if(x==y) return ;if(high[x]<high[y])par[x] = y;else{par[y] = x;if(high[x]==high[y])high[x] ++;} }void del(int x) {id[x] = idEnd ++;high[id[x]] = 0;par[id[x]] = id[x]; }bool same(int x,int y) {return find(x) == find(y); }int main() {init(7);unite(id[1],id[4]);unite(id[2],id[4]);unite(id[3],id[4]);unite(id[4],id[5]);unite(id[6],id[5]);cout << same(id[4],id[5]) << endl;del(id[4]);cout << same(id[4],id[5]) << endl;cout << same(id[1],id[5]) << endl;cout << same(id[6],id[2]) << endl;return 0; } 带删除的路径压缩并查集

 

map<string,int> IDcache; vector<string> Stringcache;int ID(string s) {if(IDcache.count(s)) return IDcache[s];Stringcache.push_back(s);return IDcache[s] = Stringcache.size()-1; } 集合映射以方便并查

 种类并查集：POJ-1182，解题策略是并查集的每个集合内的元素都同真或同假，所以每个动物就有3种可能的状态，在A或在B或在C。当第i个动物属于集合A这一命题和第j个动物属于集合B这一命题在并查集的同一集合内时，若此时出现新命题，为第i个动物和第j个动物是在同一集合内，只需要看i属于A这一状态是否和j属于B或者j属于C在并查集同一集合内，如果在同一集合内，说明两命题同真或同假，那么很显然新命题就是错误的，这样就能判定新命题的真假。

主要思想是由于动物种类的不确定，所以只能以命题的形式将多个命题通过并查集连接起来，以判断命题的真假。

 

带权并查集：主要思想是将一个并查集内的每个集合中的每个元素赋予一个权值，这个权值的意义可以是多样的，比如他与根节点的关系，或者不使用路径压缩时以他为根的权值之和。要多用一个数组，其大小就是总元素个数，来表示各种权值。

转载于:https://www.cnblogs.com/Asurudo/p/10454766.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的ACM模板——并查集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。