并查集解决的是这样一个标准问题：动态维护若干个不相交的集合，支持合并两个集合与查询两个元素是否属于同一集合。但在实际问题中，很少会直接给出“请合并集合”的题目。更多时候，我们需要先从题意中找到“连通关系”或“等价关系”，再判断题目究竟需要这种关系的什么信息。
因此，并查集题型可以沿着两条主线展开：
- 怎样识别并查集模型：对象是什么，什么算“连通”或“属于同一集合”；
- 怎样询问：求连通块数量、集合大小、判断是否成环、带权关系推断，还是扩展域的分类问题。
一、怎样从原问题中找到并查集模型
1. 显式的连通性问题
问题直接描述“连通”、“相连”、“属于同一组”等概念，是最直接的并查集应用场景。
给定 n 个人、m 对亲戚关系，以及 p 个询问，每次询问两个人是否为亲戚。亲戚关系具有传递性。
解法思路：每个人初始是一个独立的集合。每读入一对亲戚关系，就将两人所在的集合合并。查询时只需判断两人是否在同一集合中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| const int maxn=5000+5;
int f[maxn];
int n,m;
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void solve()
{
int q;
cin>>n>>m>>q;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=0;i<m;++i)
{
int x,y;
cin>>x>>y;
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
f[fx]=fy;
}
}
for(int i=0;i<q;++i)
{
int x,y;
cin>>x>>y;
if(find(x)==find(y))cout<<"Yes\n";
else cout<<"No\n";
}
}
|
2. 关系具有传递性的问题
当题目中的关系满足“A 与 B 有关系，B 与 C 有关系 ⇒ A 与 C 也有关系”时，就可以用并查集来维护这种等价关系。
给定若干对变量之间的相等/不等约束，判断是否存在一组赋值使所有约束同时满足。
数据规模较大，变量编号可达 10^9，需要离散化处理。
解法思路：将所有相等约束涉及的变量合并到同一集合，然后检查所有不等约束——如果两个变量已在同一集合中，则矛盾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| const int maxn=2e5+5;
struct Disc{
vector<int> v;
void add(int x) { v.push_back(x); }
void init()
{
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
int size() { return v.size(); }
int get_idx(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }
int get_val(int idx) { return v[idx-1]; }
};
int n;
int f[maxn];
struct node{
int x,y,op;
};
bool cmp(node a,node b)
{
return a.op>b.op;
}
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
node a[maxn];
void solve()
{
Disc disc;
cin>>n;
for(int i=0;i<n;++i)
{
int x,y,z;
cin>>x>>y>>z;
a[i]={x,y,z};
disc.add(x),disc.add(y);
}
disc.init();
sort(a,a+n,cmp);
for(int i=1;i<N;++i) f[i]=i;
int ff=1;
for(int i=0;i<n;++i)
{
auto [x,y,op]=a[i];
x=disc.get_idx(x),y=disc.get_idx(y);
int fx=find(x),fy=find(y);
if(op==1)
{
if(fx!=fy) f[fx]=fy;
}
else {
if(fx==fy)
{
ff=0;
break;
}
}
}
if(ff) cout<<"YES\n";
else cout<<"NO\n";
}
|
这一类问题的核心是：关系的传递性 = 并查集的合并。
3. 动态连通性问题（离线倒序）
并查集擅长处理动态添加边的问题，但当涉及删除/断开操作时，直接处理很困难。常用技巧是离线倒序——把删除看作反向的添加。
给定一张无向图，依次摧毁一些节点及其连边，求每次摧毁后连通块的数量。
解法思路：正着做是删边，并查集不支持这样的操作。因此离线读入所有操作，从最终状态开始倒序加边。先记录所有被摧毁的节点，建出最终剩下的图，然后倒序处理摧毁操作——每次“恢复”一个节点及其连边，用并查集合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| const int maxn=4e5+5;
int n,m;
vector<int> adj[maxn];
int fa[maxn],ans[maxn],a[maxn],vis[maxn];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void solve()
{
cin>>n>>m;
for(int i=0;i<n;++i) fa[i]=i;
for(int i=0;i<m;++i)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int k;
cin>>k;
for(int i=0;i<k;++i)
{
cin>>a[i];
vis[a[i]]=1;
}
int cnt=n-k;
for(int u=0;u<n;++u)
{
if(vis[u]) continue;
for(int v:adj[u])
{
if(vis[v]) continue;
int ru=find(u),rv=find(v);
if(ru!=rv)
{
fa[rv]=ru;
cnt--;
}
}
}
for(int i=k-1;i>=0;--i)
{
ans[i]=cnt;cnt++;vis[a[i]]=0;
int u=a[i];
for(int v:adj[u])
{
if(vis[v]) continue;
int ru=find(u),rv=find(v);
if(ru!=rv)
{
fa[rv]=ru;
cnt--;
}
}
}
cout<<cnt<<"\n";
for(int i=0;i<k;++i)
{
cout<<ans[i]<<"\n";
}
}
|
初始有 N 个同学，M 对直接朋友关系（朋友关系具有传递性，即构成无向图）。接下来 Q 个操作按时间顺序出现：
数据范围：所有测试用例的 N, M, Q 总和分别 ≤ 1.5 × 10⁵。保证初始无重边自环，每对朋友最多绝交一次。
解法思路：
并查集天生支持加边（合并），不支持删边。面对“边被逐步删除”的场景，常用技巧是 离线倒序处理：
-
记录所有绝交操作，把将来会被删除的初始边标记出来。
-
构建最终状态：只保留那些从未被绝交过的初始边，得到最后一刻的并查集。
-
从后往前回放操作：
最后把存储的答案正序输出即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| const int maxn=1e5+5;
int fa[maxn];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
struct Edge{
int op,u,v;
};
int n,m,q;
struct node{
int u,v;
};
node adj[maxn];
Edge a[maxn];
int ans[maxn];
void solve()
{
cin>>n>>m>>q;
for(int i=0;i<=n;++i) fa[i]=i;
map<pair<int,int>,int > mp;
for(int i=0;i<m;++i)
{
int u,v;
cin>>u>>v;
adj[i]={u,v};
}
for(int i=0;i<q;++i)
{
int op,u,v;
cin>>op>>u>>v;
if(u>v) swap(u,v);
if(op==1) mp[{u,v}]=1;
a[i]={op,u,v};
}
for(int i=0;i<m;++i)
{
int u=adj[i].u,v=adj[i].v;
if(mp[{u,v}]) continue;
int ru=find(u);int rv=find(v);
if(ru!=rv)
{
fa[ru]=rv;
}
}
for(int i=q-1;i>=0;--i)
{
int op=a[i].op,u=a[i].u,v=a[i].v;
if(op==2)
{
int ru=find(u);int rv=find(v);
if(ru!=rv)
{
ans[i]=0;
}
else ans[i]=1;
}
else if(op==1)
{
int ru=find(u);int rv=find(v);
if(ru!=rv)
{
fa[ru]=rv;
}
}
}
for(int i=0;i<q;++i)
{
int op=a[i].op;
if(op==2)
{
if(ans[i]) cout<<"Yes\n";
else cout<<"No\n";
}
}
}
|
给定一个包含 n 个点、m 条边的带权无向图，第 i 条边的权值为 2^i（i 从 1 开始）。你需要删掉一些边，使得图不连通，求删掉的边权值和最小是多少。
数据规模：1 <= n <= 2e5，1 <= m <= 2e5
解法思路：
删边最小化，等价于保留边最大化——在保证图不连通的前提下，尽可能保留权值大的边。
由于第 i 条边的权值是 2^i，它严格大于前面所有边的权值之和（2^1 + 2^2 + ... + 2^{i-1} < 2^i）。这个性质使得贪心策略成立：
- 从权值从大到小（即从第
m 条边到第 1 条边）依次考虑每条边；
- 如果加入这条边不会让图变得连通（即当前连通块数量 > 2），就保留它；
- 如果加入这条边会让图连通（即当前连通块数量 == 2 且这条边连接了两个不同的连通块），则不能保留，计入删掉的边权和。
用并查集维护当前图的连通性，cnt 记录当前连通块数量。初始时 cnt = n。从大到小遍历所有边：
- 若两个端点已在同一集合：这条边保留与否不影响连通性，可以直接保留（不计入答案）；
- 若两个端点在不同集合：
- 若
cnt > 2：合并两个集合，cnt--，保留这条边；
- 若
cnt == 2：此时若合并，图就变成 1 个连通块（即连通了），所以这条边必须删掉，将 2^i 加入答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| const int maxn=2e5+5,mod=998244353;
int f[maxn],v[maxn],u[maxn],cost[maxn];
int n,m;
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i];
cost[i]=(1<<i);
}
int cnt=n,ans=0;
for(int i=m;i>=1;i--)
{
rv=find(v[i]),ru=find(u[i]);
if(rv!=ru)
{
if(cnt>2)
{
cnt--;
f[rv]=ru;
}
else ans=(ans+cost[i])%mod;
}
}
cout<<ans<<"\n";
}
|
本题的关键在于两点：
- 反向思维：删边最小化 → 保留边最大化；
- 特殊边权：
2^i 的幂次性质保证了贪心策略的正确性——优先保留大边。
这与前面两题的离线倒序思路有相似之处，但本题的“倒序”体现在按边权从大到小处理，而非按时间顺序倒序。
这道题的核心是贪心 + 并查集维护连通性，属于并查集题型中的 “动态连通性 + 贪心选择” 类别。
4. 通过“反集”处理矛盾关系（扩展域并查集）
当关系不只是“同类”，还涉及“不同类”、“敌对”等二元对立关系时，可以用扩展域并查集（种类并查集）。
给定 n 个人和若干条“朋友”或“敌人”关系。朋友的朋友是朋友，敌人的敌人也是朋友。求最多有多少个团伙。
解法思路：将每个人拆成两个节点——i 表示本人，i+n 表示其敌人。
- 朋友关系：合并
i 和 j
- 敌人关系：合并
i 与 j+n，合并 i+n 与 j
最终统计集合数量即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| const int maxn=1e3+2;
int f[maxn*2];
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=2*n;++i)
{
f[i]=i;
}
for(int i=0;i<m;++i)
{
char opt;
int x,y;
cin>>opt>>x>>y;
if(opt=='F')
{
f[find(x)]=find(y);
}
else {
f[find(y+n)]=find(x);
f[find(x+n)]=find(y);
}
}
int cnt=0;
for(int i=1;i<=n;++i)
{
if(f[i]==i) cnt++;
}
cout<<cnt<<endl;
}
|
扩展域并查集的核心思想是拆点：一个元素拆成多个节点来表示不同的状态/角色。
二、怎样询问这条链（集合）
1. 仅需判断连通性
最基本的询问：两个元素是否在同一集合中，或连通块的数量。
给定 n 个村庄和 m 条已建道路，求至少还需要修多少条路才能使所有村庄连通。
解法思路：用并查集统计当前连通块数量 cnt，需要修的道路数为 cnt - 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| const int maxn=2000005;
int f[maxn];
int find(int x)
{
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}
void solve()
{
int n,m;
while(cin>>n,n)
{
cin>>m;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=0;i<m;++i)
{
int x,y;
cin>>x>>y;
int fx=find(x);
int fy=find(y);
if(fx!=fy) f[fx]=fy;
}
int ans=n-1;
for(int i=1;i<=n;++i)
{
if(f[i]!=i) --ans;
}
cout<<ans<<endl;
}
}
|
2. 需要维护集合大小/其他信息
除了连通性，有时还需要知道每个集合的大小等信息。
在一个三维空间中，有若干个半径相同的球形空洞。如果两个空洞相交或相切，则它们连通。判断是否存在一条从底部到顶部的通路。
解法思路：每个空洞是一个元素。若两个空洞相交/相切则合并。另外将底部和顶部也作为特殊节点，若空洞与底部/顶部相交则合并。最终判断底部和顶部是否在同一集合中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| typedef long long ll;
const int maxn=1e3+5;
ll n,h,r;
struct node{
ll x,y,z;
};
bool dist(node a,node b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)<=4ll*r*r;
}
node a[maxn];
struct DSU {
int fa[maxn], siz[maxn];
void init( int N ) { for( int i = 0; i <= N; ++ i ) fa[i] = i, siz[i] = 1; }
int find( int x ) { return fa[x] == x ? x : fa[x] = find( fa[x] ); }
bool merge( int x, int y ) {
int rx = find( x ), ry = find( y );
if( rx == ry ) return 0;
if( siz[rx] > siz[ry] ) swap( rx, ry );
fa[rx] = ry, siz[ry] += siz[rx];
return 1;
}
bool same( int x, int y ) { return find( x ) == find( y ); }
int size( int x ) { return siz[find( x )]; }
} dsu;
void solve()
{
cin>>n>>h>>r;
for(int i=1;i<=n;++i)
{
ll x,y,z;
cin>>x>>y>>z;
a[i]={x,y,z};
}
dsu.init(n+1);
int flag0=0,flagh=0;
for(int i=1;i<=n;++i)
{
if(a[i].z+r>=h) flagh=1,dsu.merge(i,n+1);
if(a[i].z-r<=0) flag0=1,dsu.merge(i,0);
}
if(!flag0 || !flagh)
{
cout<<"No\n";
return ;
}
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
node x=a[i],y=a[j];
if(dist(x,y))
{
dsu.merge(i,j);
}
}
}
if(dsu.same(0,n+1)) cout<<"Yes\n";
else cout<<"No\n";
}
|
3. 带权并查集：需要维护节点间的关系
当题目不仅询问“是否在同一集合”，还要求知道集合内元素之间的相对关系（如距离、差值、奇偶性等）时，需要使用带权并查集。
有 n 列战舰，支持两种操作：将某一列整体接到另一列末尾；查询两艘战舰在同一列中的距离。
解法思路：维护战舰 x 到其所在列队首（即根节点）的距离 d[x]。合并时更新被合并列的根节点的 d 值。路径压缩时累加 d 值。
1
2
3
4
5
6
7
| int find(int x)
{
if(x==fa[x]) return x;
int root=find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| const int maxn=30000+5;
int n;
int fa[maxn],d[maxn],sz[maxn];
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 solve()
{
cin>>n;
for(int i=1;i<=30000;++i) fa[i]=i,d[i]=0,sz[i]=1;
while(n--)
{
char op;
int x,y;
cin>>op>>x>>y;
int rx=find(x),ry=find(y);
if(op=='M')
{
if(rx!=ry)
{
fa[rx]=ry;
d[rx]=sz[ry];
sz[ry]+=sz[rx];
}
}
else{
if(rx!=ry) cout<<"-1\n";
else {
cout<<abs(d[x]-d[y])-1<<"\n";
}
}
}
}
|
查询两艘战舰的距离：若在同一集合中，答案为 abs(d[a] - d[b]) - 1。
动物王国中有三类动物 A、B、C，构成环形食物链：A 吃 B，B 吃 C，C 吃 A。现有 N 个动物（编号 1~N），用 K 句话描述它们之间的关系：
-
1 X Y：X 和 Y 是同类
-
2 X Y：X 吃 Y
一句话是假话当且仅当满足以下三条之一：
-
当前的话与前面某些真的话冲突
-
当前话中 X 或 Y 比 N 大
-
当前话表示 X 吃 X（即 2 X X）
数据范围：1 ≤ N ≤ 5×10⁴，1 ≤ K ≤ 10⁵。
任务：输出假话的总数。
解法思路（带权版本）：维护每个节点到根的“距离”d[x]，用 d[x] % 3 表示与根的关系（0: 同类，1: 吃根，2: 被根吃）。
要将 x 所在集合接到 y 所在集合下，已知 x 与 y 的关系为 rel（rel=0 同类，rel=1 x 吃 y）：
1
2
3
4
| x->rx->ry x->rx d[x] rx->ry d[rx]
x->y->ry x->y rel y->ry d[y]
d[x] + d[rx] ≡ d[y] + rel (mod 3)
⇒ d[rx] = (d[y] + rel - d[x] + 3) % 3
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
int fa[maxn],d[maxn];
int n,k;
int find(int x)
{
if(x==fa[x]) return x;
int p=fa[x];
int root=find(p);
d[x]=(d[x]+d[p])%3;
return fa[x]=root;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;++i) fa[i]=i,d[i]=0;
int ans=0;
while(k--)
{
int op,x,y;
cin>>op>>x>>y;
if(x>n || y>n || (op==2&&x==y))
{
ans++;continue;
}
int rx=find(x),ry=find(y);
int rel=op-1;
if(rx==ry)
{
if((d[x]-d[y]+3)%3!=rel)
{
ans++;
}
}
else{
fa[rx]=ry;
d[rx]=(rel+d[y]-d[x]+3)%3;
}
}
cout<<ans<<"\n";
}
|
解法思路（扩展域版本）：将每个动物拆成三个节点——x（自身）、x+n（猎物）、x+2n（天敌）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| const int maxn=50005;
int f[3*maxn];
int find(int x)
{
if(f[x]==x) return x;
else return f[x]=find(f[x]);
}
void solve(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n*3;i++) f[i]=i;
int cnt=0;
for(int i=0;i<k;++i)
{
int z,x,y;
cin>>z>>x>>y;
if(x>n||y>n)
{
cnt++;
continue;
}
if(z==1)
{
if(f[find(x)]==f[find(y+n)]||f[find(y)]==f[find(x+n)]) cnt++;
else
{
f[find(x)]=find(y);
f[find(x+n)]=find(y+n);
f[find(x+2*n)]=find(y+2*n);
}
}
else if(z==2)
{
if(f[find(x)]==f[find(y)]||f[find(y)]==find(x+n)) cnt++;
else
{
f[find(x)]=find(y+n);
f[find(x+n)]=find(y+2*n);
f[find(x+2*n)]=find(y);
}
}
}
cout<<cnt<<endl;
}
|
要点总结
| 题型 |
维护的权值含义 |
合并公式特征 |
代表题目 |
| 距离/位置 |
到根的距离（差值） |
d[rx] = sz[ry] |
P1196 银河英雄传说 |
| 模数/循环 |
模 k 的余数（同类/天敌） |
d[rx] = (d[y] + w - d[x]) % k |
P2024 食物链 |
| 异或/奇偶 |
0 或 1（相同/不同） |
d[rx] = d[y] ^ w ^ d[x] |
P5937 Parity Game |
| 比例/商 |
倍数关系 |
d[rx] = d[y] * w / d[x] |
LeetCode 399 |
-
明确 d[x] 的定义：它表示 x 到父节点的关系，路径压缩后会变成到根的关系。
-
记住 find 中要保存父节点：int p = fa[x];，这是避免错误的铁律。
-
推导合并公式：画图，用向量思维 x → rx → ry → y 推导 d[rx]。
-
检查模运算：C++ 负数取模为负，需要 (a % mod + mod) % mod 转换。
-
判断何时使用：题目中出现“差值”、“距离”、“奇偶”、“倍数”、“A 吃 B”等相对关系时，优先考虑带权并查集。
4. 扩展域并查集：需要维护多种关系/状态
当关系不止“同类/不同类”两种，而是有多种类型时（如食物链中的三类关系），可以用扩展域并查集。
给定一个 01 序列，每次询问区间 [l, r] 中 1 的个数是奇数还是偶数。判断最多前多少条询问可以同时满足。
数据规模：序列长度 <= 10^9，询问数 <= 5000。
解法思路：用前缀和 S[i]。询问 [l, r] 中 1 的个数为奇数 ⇔ S[l-1] 与 S[r] 奇偶性不同。将每个前缀和拆成两个节点（奇/偶），用扩展域并查集维护约束。注意 N 很大但询问数很少，需要离散化。
带权 vs 扩展域的选择：
- 带权并查集：适合维护数值关系（距离、差值等），如银河英雄传说；
- 扩展域并查集：思维量较小，适合维护逻辑关系（同类/不同类/多种分类），如食物链、关押罪犯、Parity Game。
5. 并查集与其他算法结合
并查集常作为工具与其他算法配合使用：
- Kruskal 最小生成树：用并查集判断加入边是否成环；
- 离线查询 + 排序：将询问按某种顺序排序后动态维护连通性；
- ST 表优化建图：对于区间一一对应的约束，用 ST 表分块 + 并查集优化连边。
三、题型框架总结
| 题型分类 |
核心特征 |
代表题目 |
| 模板/基础连通性 |
合并与查询 |
P3367 【模板】并查集 |
| 普通连通性 |
求连通块数量/判断连通 |
P1551 亲戚、P1536 村村通、P3958 奶酪 |
| 离线倒序 |
删边转加边 |
P1197 星球大战、米秋的贴吧吃瓜、ABC447E |
| 维护集合信息 |
集合大小等附加信息 |
P3958 奶酪 |
| 扩展域并查集 |
拆点表示多种状态/关系 |
P1892 团伙、P1525 关押罪犯、P2024 食物链、P5937 Parity Game |
| 带权并查集 |
维护节点到根的数值关系 |
P1196 银河英雄传说、P2024 食物链 |
| 并查集 + 其他算法 |
作为子模块配合使用 |
Kruskal 最小生成树、ST 表优化建图 |
并查集本身代码极短，难点在于抽象能力——能否把原始问题抽象成集合的合并与查询。做题时可以先问自己三个问题：
- 谁是元素？——问题中的基本对象是什么；
- 什么算连通？——两个对象在什么条件下属于同一集合；
- 问什么？——是问连通性、集合大小、相对关系，还是多种状态的分类？
