并查集解决的是这样一个标准问题：动态维护若干个不相交的集合，支持合并两个集合与查询两个元素是否属于同一集合。但在实际问题中，很少会直接给出“请合并集合”的题目。更多时候，我们需要先从题意中找到“连通关系”或“等价关系”，再判断题目究竟需要这种关系的什么信息。

因此，并查集题型可以沿着两条主线展开：

  • 怎样识别并查集模型：对象是什么，什么算“连通”或“属于同一集合”；
  • 怎样询问：求连通块数量、集合大小、判断是否成环、带权关系推断，还是扩展域的分类问题。

一、怎样从原问题中找到并查集模型

1. 显式的连通性问题

问题直接描述“连通”、“相连”、“属于同一组”等概念，是最直接的并查集应用场景。

典型例题：P1551 亲戚

给定 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 也有关系”时，就可以用并查集来维护这种等价关系。

典型例题：P1955 程序自动分析

给定若干对变量之间的相等/不等约束，判断是否存在一组赋值使所有约束同时满足。

数据规模较大，变量编号可达 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. 动态连通性问题（离线倒序）

并查集擅长处理动态添加边的问题，但当涉及删除/断开操作时，直接处理很困难。常用技巧是离线倒序——把删除看作反向的添加。

典型例题：P1197 [JSOI2008] 星球大战

给定一张无向图，依次摧毁一些节点及其连边，求每次摧毁后连通块的数量。

解法思路：正着做是删边，并查集不支持这样的操作。因此离线读入所有操作，从最终状态开始倒序加边。先记录所有被摧毁的节点，建出最终剩下的图，然后倒序处理摧毁操作——每次“恢复”一个节点及其连边，用并查集合并。

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";
    }
}

典型例题：9619: 米秋的贴吧吃瓜

初始有 N 个同学，M 对直接朋友关系（朋友关系具有传递性，即构成无向图）。接下来 Q 个操作按时间顺序出现：

  • 1 U V：U 和 V 绝交（删除这条直接边）；

  • 2 U V：查询 U 和 V 当前是否还在同一个交际圈（即是否连通）。

数据范围：所有测试用例的 N, M, Q 总和分别 ≤ 1.5 × 10⁵。保证初始无重边自环，每对朋友最多绝交一次。

解法思路：

并查集天生支持加边（合并），不支持删边。面对“边被逐步删除”的场景，常用技巧是 离线倒序处理：

  1. 记录所有绝交操作，把将来会被删除的初始边标记出来。

  2. 构建最终状态：只保留那些从未被绝交过的初始边，得到最后一刻的并查集。

  3. 从后往前回放操作：

    • 遇到查询 2 U V：直接用当前并查集回答，存储答案。

    • 遇到绝交 1 U V：恢复这条边（因为倒序看，这条边是在这个时刻被删除的，往前它就是存在的），执行 unite(U, V)。

最后把存储的答案正序输出即可。

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";
		}
	}
}

典型例题：ABC447 E - Divide Graph

给定一个包含 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";
}

本题的关键在于两点：

  1. 反向思维：删边最小化 → 保留边最大化；
  2. 特殊边权：2^i 的幂次性质保证了贪心策略的正确性——优先保留大边。

这与前面两题的离线倒序思路有相似之处，但本题的“倒序”体现在按边权从大到小处理，而非按时间顺序倒序。

这道题的核心是贪心 + 并查集维护连通性，属于并查集题型中的 “动态连通性 + 贪心选择” 类别。

4. 通过“反集”处理矛盾关系（扩展域并查集）

当关系不只是“同类”，还涉及“不同类”、“敌对”等二元对立关系时，可以用扩展域并查集（种类并查集）。

典型例题：P1892 [BOI2003] 团伙

给定 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. 仅需判断连通性

最基本的询问：两个元素是否在同一集合中，或连通块的数量。

典型例题：P1536 村村通

给定 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. 需要维护集合大小/其他信息

除了连通性，有时还需要知道每个集合的大小等信息。

典型例题：P3958 [NOIP2017 提高组] 奶酪

在一个三维空间中，有若干个半径相同的球形空洞。如果两个空洞相交或相切，则它们连通。判断是否存在一条从底部到顶部的通路。

解法思路：每个空洞是一个元素。若两个空洞相交/相切则合并。另外将底部和顶部也作为特殊节点，若空洞与底部/顶部相交则合并。最终判断底部和顶部是否在同一集合中。

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. 带权并查集：需要维护节点间的关系

当题目不仅询问“是否在同一集合”，还要求知道集合内元素之间的相对关系（如距离、差值、奇偶性等）时，需要使用带权并查集。

典型例题：P1196 [NOI2002] 银河英雄传说

有 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];
//d[x]表示x 到其所在列队根节点的距离
//sz[x]表示x的战舰总数
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。

典型例题：P2024 [NOI2001] 食物链

动物王国中有三类动物 A、B、C，构成环形食物链：A 吃 B，B 吃 C，C 吃 A。现有 N 个动物（编号 1~N），用 K 句话描述它们之间的关系：

  • 1 X Y：X 和 Y 是同类

  • 2 X Y：X 吃 Y

一句话是假话当且仅当满足以下三条之一：

  1. 当前的话与前面某些真的话冲突

  2. 当前话中 X 或 Y 比 N 大

  3. 当前话表示 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

  1. 明确 d[x] 的定义：它表示 x 到父节点的关系，路径压缩后会变成到根的关系。

  2. 记住 find 中要保存父节点：int p = fa[x];，这是避免错误的铁律。

  3. 推导合并公式：画图，用向量思维 x → rx → ry → y 推导 d[rx]。

  4. 检查模运算：C++ 负数取模为负，需要 (a % mod + mod) % mod 转换。

  5. 判断何时使用：题目中出现“差值”、“距离”、“奇偶”、“倍数”、“A 吃 B”等相对关系时，优先考虑带权并查集。

4. 扩展域并查集：需要维护多种关系/状态

当关系不止“同类/不同类”两种，而是有多种类型时（如食物链中的三类关系），可以用扩展域并查集。

典型例题：P5937 [CEOI1999] Parity Game

给定一个 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 表优化建图

并查集本身代码极短，难点在于抽象能力——能否把原始问题抽象成集合的合并与查询。做题时可以先问自己三个问题：

  1. 谁是元素？——问题中的基本对象是什么；
  2. 什么算连通？——两个对象在什么条件下属于同一集合；
  3. 问什么？——是问连通性、集合大小、相对关系，还是多种状态的分类？