并查集简介
并查集是一种可以动态维护若干个不重叠的结合，并支持合并与查询的数据结构
并查集是一种树状的数据结构，可以用于维护传递关系以及联通性。
并查集有两种操作：
find：查询一个元素属于哪个集合merge:合并两个集合
模板
find函数
int find(int x)
{
if(x == fa[x]) return x;
reutnr fa[x] = find(fa[x]);
}
merge函数
void merge(int x, int y)
{
int px = find(x), py = find(y);
if(px != py) fa[px] = py;
}
模板题
村村通
对于这道题我们只需要求连通块的数量，然后将这几个联通快看成点，联通n个点需要n-1条边
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int p[N], st[N];
int find(int x)
{
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
int main()
{
// freopen("1.in", "r", stdin);
while(1)
{
memset(st, 0, sizeof st);
int n, ans = 0;
scanf("%d", &n);
if(n == 0) return 0;
else
{
int m; scanf("%d", &m);
for(int i = 1; i <= n; ++ i) p[i] = i;
for(int i = 0; i < m; ++ i)
{
int x, y; scanf("%d%d", &x, &y);
int a = find(x);
int b = find(y);
if(a != b) p[a] = b;
}
//统计联通块的数量
for(int i = 1; i <= n; ++ i)
{
int x = find(i);
if(!st[x]) ans ++, st[x] = 1;;
}
cout << ans - 1 << endl;
}
}
}
P1551 亲戚
亲戚的亲戚是亲戚，亲戚这种关系具有传递性，如果具有亲戚关系就将合并。
#include <iostream>
using namespace std;
const int N = 5010;
int p[N];
int n, m, t;
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m >> t;
for(int i = 1; i <= n; ++ i) p[i] = i;
for(int i = 0; i < m; ++ i)
{
int a, b;cin >> a >> b;
int fa = find(a);
int fb = find(b);
p[fa] = fb;
}
for(int i = 0; i < t; ++ i)
{
int a, b;cin >> a>> b;
int fa = find(a);
int fb = find(b);
if(fa != fb) puts("No");
else puts("Yes");
}
return 0;
}
#include <iostream>
using namespace std;
const int N = 1e5+10;
int n,m;
int p[N];
int find(int x)
{
if(p[x] != x ) p[x] = find(p[x]);
return p[x];
}
int main(int argc, const char * argv[]) {
scanf("%d%d",&n,&m);
for(int i = 0; i < n; i ++) p[i] = i;
while(m--)
{
char op[2];int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0] == 'M') p[find(a)] = find(b);
else
{
if(find(a) == find(b)) cout<<"Yes"<<endl;
else puts("No");
}
}
return 0;
}
837. 连通块中点的数量
这道题目比前面的几道模板题目需要多维护一个信息，在进行merge时我们需要将更新作为被添加枝的树的cnt
两个bug调了一个小时最后看了下评论区收获颇丰
1、合并两个集合时
如果没有按照下面的写法即省去这一步a=find(a),b=find(b);
则合并根节点的顺序与更新更新集合得顺寻不能互换，
必须要先把原来根节点中元素的数量加到所要合并的
根节点上去再把根节点合并
a=find(a),b=find(b);
cnt[b]+=cnt[a];
p[a]=b;
2、路径压缩
一定不要忘记路径压缩不然会超时！！！
#include"bits/stdc++.h"
using namespace std;
const int N=1e5+10;
int p[N],cnt[N];
int n,m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) {p[i]=i;cnt[i]=1;}
while(m--)
{
string str;
int a,b;
cin>>str;
if(str=="C")
{
cin>>a>>b;
if(find(a)!=find(b))
{
a=find(a),b=find(b);
cnt[b]+=cnt[a];
p[a]=b;
}
}
else if(str=="Q1")
{
cin>>a>>b;
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else
{
cin>>a;
cout<<cnt[find(a)]<<endl;
}
}
return 0;
}
边带权并查集
推导部分和
这道题的是带边权并查集的应用，比较难想到的是建图
对于每个区间l, r，k, 我们可以由前缀和s[r] - s[l - 1] = k，我们从r连一条l-1的边
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
//p[N]数组用来做并查集
int p[N], n, m, q;
//s[N]数组是当前点到根结点的权值和，也是前缀和
LL s[N];
//并查集的查询操作（带路径压缩）
int find(int x)
{
if(x == p[x]) return x;
else
{
int t = find(p[x]);
s[x] += s[p[x]];
p[x] = t;
return t;
}
}
int main()
{
// freopen("1.in", "r", stdin);
cin >> n >> m >> q;
for(int i = 1; i <= n; ++ i) p[i] = i;
for(int i = 0; i < m; ++ i)
{
int l ,r;
LL k;
cin >> l >> r >> k;
int t1 = find(l - 1), t2 = find(r);
if(t1 != t2)
{
p[t2] = t1;
s[t2] = s[l - 1] - s[r] + k;
}
}
while(q --)
{
int l, r;cin >> l >> r;
int t1 = find(l - 1), t2 = find(r);
if(t1 != t2) puts("UNKNOWN");
else printf("%lld\n", s[r] - s[l - 1]);
}
return 0;
}
P1196 [NOI2002] 银河英雄传说
这道题目比较特殊是每个集合是一条链，一条链也是一棵树，不过是树的特殊形态，我们可以把每一列看作一个集合，用并查集去维护，另外题目中需要知道两个点之间的点有多少个，这里我们就还需要额外维护每个点到根节点路径上的权值，因为我们这里的并查集已经进行优化即使用了路径压缩，并且边权都是1，所以在维护每个点到根节点的路径上的权值时，我们还需要用到一个集合中元素的个数，也就是还需要额外维护集合中元素个数。
综上我们需要额外维护两个信息：
d[x]:表示x到根节点的边权求和size[x]:表示以x为根的子树中节点数量
#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define db double
using namespace std;
const int N = 30010;
int fa[N], d[N], size[N],t;
void init()
{
for(int i = 1; i <= N - 1; ++ i) fa[i] = i, size[i] = 1;
}
int find(int x)
{
if(x == fa[x]) return x;
int root = find(fa[x]);
d[x] += d[fa[x]];
return fa[x] = root;
}
void merge(int x, int y)
{
int px = find(x), py = find(y);
if(px == py) return;
fa[px] = py;
d[px] = size[py];
size[py] += size[px];
}
void solve()
{
cin >> t;
init();
for(int i = 1; i <= t; ++ i)
{
char op;
int x, y;
cin >> op >> x >> y;
if(op == 'M') merge(x, y);
else
{
int px = find(x), py = find(y);
if(px != py) cout << -1 << endl;
else cout << abs(d[x] - d[y]) - 1 << endl;
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
// cin >> t;
// while(t --)
solve();
return 0;
}
并查集的拓展域
P2024 [NOI2001] 食物链
这是一道并查集的拓展域的题目也可以用带权并查集去做
普通并查集维护的是不相交集合，是一种传递性的关系如亲戚的亲戚是亲戚
天敌的天敌是食物，是一种环形的关系
我们如果用拓展域来解决这道题目的话可以用3个并查集来维护3种关系，第一种是同类关系，第二种是食物关系，第三种是天敌
我们不用真开三个并查集，我们可以将三个并查集开到一个数组里，下标的范围代表不同的集合
#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int p[N * 3], ans, k, n;
//1--n代表x的同类，n + 1 -- 2n代表x的食物， 2n + 1 -- 3n代表x的天敌
int find(int x)
{
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
void merge(int x, int y)
{
int px = find(x), py = find(y);
p[py] = px;
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= 3 * n; ++ i) p[i] = i;
for(int i = 0; i < k; ++ i)
{
int d, x, y;scanf("%d%d%d", &d, &x, &y);
if(x > n || y > n) ans ++;
//x、y是同类
else if(d == 1)
{
//如果根据前面的信息，我们可以知道y在x的食物域，
//或者y在x的天敌域中，说明这句话是假话
if(find(x + n) == find(y) || find(x + n + n) == find(y)) ans ++;
//如果根据前面的信息，不能判断这句话是错误的，那么就讲这句话
//当成对的并且更新x的三个域
else
{
//y在x的同类域中
merge(x, y);
//y的食物和x的食物是同类
merge(x + n, y + n);
//y的天敌和x的天敌是同类
merge(x + n + n, y + n + n);
}
}
//如果x吃y
else
{
//若果y在x的同类域或者，y在x的天敌域说明这句话是假话
if(find(x) == find(y) || find(x + n + n) == find(y)) ans ++;
//这句话是真话就更新x的三个域
else
{
//y在x的食物域中
merge(x + n, y);
//y的食物是x的天敌
merge(x + n + n, y + n);
//y的天敌是x的同类
merge(x, y + n + n);
}
}
}
cout << ans << endl;
return 0;
}
#include <iostream>
using namespace std;
const int N = 2010;
int p[N];
bool st[N];
int find(int x)
{
if(p[x] == x) return p[x];
return p[x] = find(p[x]);
}
void merge(int x, int y)
{
int px = find(x), py = find(y);
if(px != py) p[px] = py;
}
int main()
{
// freopen("1.in", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= 2 * n; ++ i) p[i] = i;
for(int i = 0; i < m; ++ i)
{
char op; int x, y;
cin >> op >> x >> y;
if(op == 'F')
{
merge(x, y);
// merge(x + n, y + n);
}
else
{
merge(x + n, y);
merge(x, y + n);
}
}
// for(int i = 1; i <= n; ++ i) cout << i << ' ' << find(i) << endl;
int cnt = 0;
for(int i = 1; i <= n; ++ i)
if(!st[find(i)])
{
cnt ++;
st[find(i)] = 1;
}
cout << cnt << endl;
return 0;
}
题目的具体思路如下：考虑一段连续区间的1个数的奇偶，可以转化为考虑考虑两个端点前缀和的奇偶性上，分为两种情况，如果[l, r]区间内1的个数为偶数，说明sum[r]和sum[l - 1]包含1的个数的奇偶性相同，反之若为奇数则两个包含1的个数的奇偶性相反，我们知道奇偶性具有传递性，这样我们就可以种类并查集来维护，注意n的范围比较大，但是实际的需要用到的点的个数是比较小的，这里我们需要离散化一下。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e4 + 10;
int p[N * 2 + 10], n, m, k;
map<int, int>mp;
int b[N * 2];
struct wy
{
int l, r, op;
}q[N];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)
{
int px = find(x), py = find(y);
p[py] = px;
}
int query(int x)
{
return lower_bound(b + 1, b + 1 + k, x) - b;
}
void solve()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
{
int l, r, op;
char s[5];
scanf("%d%d%s", &l, &r, s);
if(s[0] == 'e') op = 1;
else op = 2;
q[i] = {--l, r, op};
b[++ k] = l;
b[++ k] = r;
}
sort(b + 1, b + 1 + k);
k = unique(b + 1, b + 1 + k) - (b + 1);
for(int i = 1; i <= 2 * k; ++ i) p[i] = i;
for(int i = 1; i <= m; ++ i)
{
int l = query(q[i].l), r = query(q[i].r), op = q[i].op;
if(op == 1)
{
if(find(l) == find(r + k) || find(r) == find(l + k))
{
printf("%d", i - 1);
return;
}
else
{
merge(l, r);
merge(l + k, r + k);
}
}
else
{
if(find(l) == find(r) || find(r + k) == find(l + k))
{
printf("%d", i - 1);
return;
}
else
{
merge(l, r + k);
merge(r, l + k);
}
}
}
printf("%d", m);
}
int main()
{
// freopen("1.in", "r", stdin);
solve();
return 0;
}
应用
这道题目是相等关系，相等关系也具有传递性，明显我们可以用并查集来维护。
我们可以先对处理相等，然后去查询不相等的是否在一个集合里面如果在一个集合里面则说明这样的点是不存在的。这道题目的数据的范围很大，但实际用到的很少，我们需要对数据进行离散化。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e6 + 10;
int n, m, p[N], a[N], k, tot;
struct wy{
int x, y, e;
}q[N];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)
{
int px = find(x), py = find(y);
p[py] = px;
}
void solve()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
int x, y, e;
scanf("%d%d%d", &x, &y, &e);
a[++ tot] = q[i].x = x;
a[++ tot] = q[i].y = y;
q[i].e = e;
}
sort(a + 1, a + 1 + tot);
tot = unique(a + 1, a + 1 + tot) - a - 1;
for(int i = 1; i <= tot; ++ i) p[i] = i;
for(int i = 1; i <= n; ++ i)
{
q[i].x = lower_bound(a + 1, a + tot + 1, q[i].x) - a - 1;
q[i].y = lower_bound(a + 1, a + tot + 1, q[i].y) - a - 1;
if(q[i].e == 1){
merge(q[i].x, q[i].y);
}
}
for(int i = 1; i <= n; ++ i){
int x = q[i].x;
int y = q[i].y;
if(q[i].e == 0 && find(x) == find(y)){
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d", &k);
while(k--) solve();
return 0;
}
P1525 [NOIP2010 提高组] 关押罪犯
贪心+并查集，我们优先选择边权最大的罪犯，首先查询他们是否已经在一个集合 如果不在，分别将他们放进不同监狱（集合），如果在则说明我们已经找到了答案
#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define db double
using namespace std;
const int N = 1e6 + 10, e = 20010;
struct wy
{
int x, y, val;
bool operator < (const wy & t) const
{
return t.val < val;
}
}a[N];
int p[N + 1];
int n, m;
void init()
{
for(int i = 1; i <= N; ++ i) p[i] = i;
}
int find(int x)
{
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
void merge(int x, int y)
{
int px = find(x), py = find(y);
if(px != py) p[py] = px;
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; ++ i)
{
int x, y, val; cin >> x >> y >> val;
a[i] = {x, y, val};
}
sort(a + 1, a + 1 + m);
init();
for(int i = 1; i <= m; ++ i)
{
int x = a[i].x, y = a[i].y, val = a[i].val;
int px = find(x), py = find(y);
if(px == py)
{
cout << val << endl;
return;
}
else
{
merge(y + n, x);
merge(x + n, y);
}
}
cout << 0 << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
// cin >> t;
// while(t --)
solve();
return 0;
}