数据结构-并查集专题（1）

一、前言

因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛，于是开始按专题梳理一下对应的知识点，先从简单入门又值得记录的内容开始，并查集首当其冲。

二、我的模板

虽然说是借用了jiangly鸽鸽的板子，但是自己也小做修改了部分（命名啥的，大体内容并没有修改，jiangly鸽鸽yyds）

#include <bits/stdc++.h>struct DisjointSet {int _n;std::vector<int> _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) {_fa[x] = find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fx]+=_size[fy];_fa[fy] = fx;return true;}return false;}
};

三、并查集介绍

并查集（disjoint set），英文直译过来是不相交的集合。我们中文取名成并查集，是因为这类集合主要具有两个操作：并和查，并即合并两个集合，查即查询集合的某些信息。

3.1 并

如果有学习过树的知识，那么理解并查集就比较轻松了。“并”操作类似于将森林（两棵树）转化为一棵树，我们只需要让其中一个并查集的根节点的父亲结点指向另外一个并查集的根节点即可。当然选择的时候，我们倾向于让深度小的树的根节点指向深度大的树的根节点。不过后续用上路径压缩后，谁指向谁基本没有什么太大的影响。实际写代码中，我们主要的操作就是对一个并查集的根节点进行修改

3.2 查

1.查询某个节点的根节点 2.查询两个节点是否处于同一个并查集中 3.查询一共有几个并查集 4.查询节点数量最多的并查集和它的节点数量 5.查询节点位于自身并查集的深度

3.3 初始化

在没有进行任何合并前，一个并查集的根节点应该为它自身（切记写代码的时候不要忘记并查集的初始化，当然如果用我的模板的话就不会忘记初始化，构造函数已经写好初始化了）

3.4 路径压缩

正常来说，并查集合并的时间复杂度为O(1)，而查询的最坏时间复杂度为O(n)，常见的最坏情况就是只有左子树或者只有右子树的一棵树的查询。而如果我们在查询时顺带将查询路径上的结点的父节点属性顺带修改为真正的根节点，那么综合下来，时间复杂度将会被均摊成O(logn)，这是一个非常优秀的优化。

四、专题训练

以我学校OJ题目展开训练

4.1 题目总览

4.2 1520: 数据结构-并查集-家庭问题

思路

这道题是很典型的用并查集做的题目，先对并查集进行初始化，我们直接把有关系的两人进行合并，如果已经处于同一个并查集中则不做操作。后续题目需要我们查询的是并查集的数量以及并查集中最大的节点数量

参考代码

前面都是并查集模板，注意构造并查集的时候至少把节点数+1（因为用于实现的vetcor下标从0开始，大部分题目的下标是从1开始的），最后查询的时候利用set进行排序输出即可

#include <bits/stdc++.h>
using i64 = long long;struct DisjointSet {int _n;std::vector<int> _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) _fa[x] = find(_fa[x]);return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fy]+=_size[fx];_fa[fx] = fy;return true;}return false;}
};
using pii = std::pair<int,int>;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,k;std::cin >> n >> k;DisjointSet disjointSet = DisjointSet(n+1);for(int i = 0;i<k;i++) {int mem1,mem2;std::cin >> mem1 >> mem2;disjointSet.merge(mem1,mem2);}std::set<pii> st;for(int i = 1;i<=n;i++) {int t = disjointSet.find(i);st.insert(std::make_pair(disjointSet._size[t],t));}std::cout << st.size() << ' ' << (*st.rbegin()).first << '\n';return 0;
}

4.3 1565: 并查集-团伙

思路

这个题由于enemy的存在，需要多维护一个ene[]数组，ene[]数组初始化为0，如果遇到p等于0的时候，分别判断x和y的ene是否为0，如果为0，则代表他们当前没有enemy，则把ene值设置成对方，即x和y分别属于两个并查集中，如果当前存在ene，那么就把自己合并到他们enemy的并查集中，因为敌人的敌人是朋友。至于p等于1的情况，当做正常并查集的合并来做。最后输出并查集的数量（计算父节点等于自身的节点数量）即可

参考代码

#include <bits/stdc++.h>
using i64 = long long;struct DisjointSet {int _n;std::vector<int> _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) {_fa[x] = find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fy]+=_size[fx];_fa[fx] = fy;return true;}return false;}
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,m;std::cin >> n >> m;DisjointSet disjointSet = DisjointSet(n+1);std::vector<int> ene(n+1,0);for(int i = 0;i<m;i++) {int t,x,y;std::cin >> t >> x >> y;if(t) {//enemyif(ene[x]) {disjointSet.merge(y,ene[x]);}else {ene[x] = y;}if(ene[y]) {disjointSet.merge(x,ene[y]);}else {ene[y] = x;}}else {//frienddisjointSet.merge(x,y);}}int ans = 0;for(int i = 1;i<=n;i++) {if(disjointSet.find(i)==i) ++ans;}std::cout << ans << '\n';return 0;
}

4.4 1566: 并查集-打击犯罪

思路

题目有点反直觉，我一开始想着从1到k依次进行判断，断开某个关系后可以使得他们中最大的一个危险程度小于等于n/2，然后后来发现写起来很困难。正难则反，因此我们考虑从n开始循环，跑到1结束，每次循环让这个循环变量i这个节点和它有关系并且大于k的j节点进行合并，然后看看是否有危险程度大于n/2的并查集即可。

参考代码

#include <bits/stdc++.h>
using i64 = long long;struct DisjointSet {int _n;std::vector<int> _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) {_fa[x] = find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fx]+=_size[fy];_fa[fy] = fx;return true;}return false;}
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;std::vector<std::vector<int>> edges(n+1,std::vector<int>());DisjointSet disjointSet = DisjointSet(n+1);for(int i = 0;i<n;i++) {int siz;std::cin >> siz;for(int j = 0;j<siz;j++) {int t;std::cin >> t;edges[i+1].emplace_back(t);}}for(int k = n;k>=1;k--) {for(auto &edge:edges[k]) {if(edge>k) {disjointSet.merge(k,edge);}}if(disjointSet._size[disjointSet.find(k)]>n/2) {std::cout << k << '\n';return 0;}}return 0;
}

4.5 1567: 并查集-搭配购买

思路

并查集+01背包，中间对数据的存储搞得我很头疼，用了一堆vector，先把c[]和d[]数组存起来，做了并查集的合并后，再算一个并查集c[]的总和sumc[]以及d[]的总和sumd[]，然后把计算好的总和放进real_c[]和real_d[]数组中，再使用一个dp[]数组做一遍01背包，最后的dp[w]输出即可

参考代码

#include <bits/stdc++.h>
using i64 = long long;struct DisjointSet {int _n;std::vector<int> _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) {_fa[x] = find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fx]+=_size[fy];_fa[fy] = fx;return true;}return false;}
};
using pii = std::pair<int,int>;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,m,w;std::cin >> n >> m >> w;std::vector<int> c,d;for(int i = 0;i<n;i++) {int tmpc,tmpd;std::cin >> tmpc >> tmpd;c.emplace_back(tmpc);d.emplace_back(tmpd);}DisjointSet disjointSet = DisjointSet(n+1);for(int i = 0;i<m;i++) {int x,y;std::cin >> x >> y;disjointSet.merge(x,y);}std::vector<int> sumc(n+1,0),sumd(n+1,0);for(int i = 1;i<=n;i++) {int t = disjointSet.find(i);sumc[t] += c[i-1];sumd[t] += d[i-1];}std::vector<int> real_c,real_d;for(int i = 1;i<=n;i++) {if(sumc[i]!=0) {real_c.emplace_back(sumc[i]);real_d.emplace_back(sumd[i]);}}std::vector<int> dp(w+1,0);for(int i = 0;i<real_c.size();i++) {for(int j = w;j>=real_c[i];j--) {dp[j] = std::max(dp[j],dp[j-real_c[i]]+real_d[i]);}}std::cout << dp[w] << '\n';return 0;
}

五、后记

剩下的题目及并查集的进一步运用（求最小生成树的Kruskal算法）见后续的（2）