[Solution] 并查集题型整理

[L5] 并查集题型整理

这份笔记作为并查集的主入口，按「问题模型」整理。

主线是：先用普通并查集维护连通块，再把关系编码成扩展域，再把关系压成带权差值，最后处理队列合并这种特殊位置模型。

一、连通块问题

这一类是并查集的最典型应用，核心在于判断点是否处在同一个连通块内，或者维护连通块数量。

常见变化有三种(暂时整理)：

  1. 离散化约束：变量值域很大，但出现的变量有限，先离散化再合并。
  2. 二分答案 + 连通性检查：答案具有单调性，每次 check 用并查集判断是否形成阻断或连通。
  3. 反向加点 / 加边：正着删点不好维护，倒着恢复点，把分裂问题变成合并问题。

连通块模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 并查集：路径压缩 + 按大小合并
struct DSU {
/* ======================================== */
int fa[maxn], siz[maxn];
void init( int N ) { for( int i = 1; 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;

1. P1955 [NOI2015] 程序自动分析

题意

给定若干约束，每条约束形如 xi=xjx_i = x_j 或 xi≠xjx_i \neq x_j，判断这些约束能否同时成立。

约束数量 n≤1e5n \le 1e5，变量编号值域很大，需要离散化。

思路

相等关系具有传递性，所以先把所有 xi=xjx_i = x_j 的约束合并起来，得到完整的相等闭包。

变量编号值域很大，但一组数据中真正出现的变量最多只有 2n2n 个，所以先用离散化把原变量编号映射成连续下标。

最后再检查所有 xiexjx_i e x_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
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;

/* ============================== */
struct Disc { /* 板子略 */ } disc;
struct DSU { /* 板子略 */ } dsu;
/* ============================== */

struct Opt { int i, j, c; };

void solve( ) {
    int n;
    cin >> n;

    bool ok = 1;
    vector<Opt> a(n + 1);

    disc.clear( );
    for( int i = 1; i <= n; ++ i ) {
        cin >> a[i].i >> a[i].j >> a[i].c;
        disc.add( a[i].i );
        disc.add( a[i].j );
    }
    disc.init( );
    dsu.init( disc.size( ) );

    for( int i = 1; i <= n; ++ i ) {
        auto [x, y, c] = a[i];
        int dx = disc.get_idx( x ), dy = disc.get_idx( y );
        if( c == 1 ) dsu.merge( dx, dy );
    }
    
    for( int i = 1; i <= n; ++ i ) {
        auto [x, y, c] = a[i];
        int dx = disc.get_idx( x ), dy = disc.get_idx( y );
        if( c == 0 ) if( dsu.same( dx, dy ) ) ok = 0;
    }
    
    cout << ( ok ? "YES" : "NO" ) << '\n';
}

2. P1783 海滩防御

题意

给定一个宽度为 nn 的区域和若干个灯塔。每个灯塔的照亮半径为 rr，如果灯塔照亮区域从左边界连通到右边界，就会形成阻断。求最小的阻断半径。

思路

答案 rr 具有单调性：如果半径 rr 已经能阻断，那么更大的半径也一定能阻断。因此可以二分答案。

对于固定的 rr，用并查集判断所有灯塔照亮区域之间是否相交。如果两个灯塔距离不超过 2r2r，就把它们合并。

额外建立两个虚拟点：左边界 L 和右边界 R；如果某个灯塔距离左边界不超过 rr，就和 L 合并；距离右边界不超过 rr，就和 R 合并。

最后如果 L 和 R 连通，说明这个半径已经能形成阻断。

此处左右端点和灯塔之间的距离是 rr，而两个灯塔之间的距离是 2r2r。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 800 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct DSU { /* 板子略 */ } dsu;
/* ============================== */

struct Point {
    double x, y;
} ps[maxn];

bool check( double r, int n, int m ) {
    int L = 0, R = m + 1;
    dsu.init( m + 1 );
    for( int i = 1; i <= m; ++ i ) {
        if( ps[i].x <= r ) dsu.merge( i, L );
        if( n - ps[i].x <= r ) dsu.merge( i, R );
    }
    for( int i = 1; i <= m; ++ i ) {
        for( int j = i + 1; j <= m; ++ j ) {
            double dx = ps[i].x - ps[j].x, dy = ps[i].y - ps[j].y;
            if( dx * dx + dy * dy <= 4.0 * r * r ) dsu.merge( i, j );
        }
    }
    return dsu.same( L, R );
}

void solve( ) {
    ll n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) ps[i].x = read( ), ps[i].y = read( );
    double l = 0, r = 200000;
    for( int t = 1; t <= 100; ++ t ) {
        double mid = ( l + r ) / 2.0;
        if( check( mid, n, m ) ) r = mid;
        else l = mid;
    }
    cout << fixed << setprecision( 2 ) << r << '\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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 4e5 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct DSU { /* 板子略 */ } dsu;
/* ============================== */

vector<int> adj[maxn];
bool broken[maxn]; // break;
int ans[maxn];
int ks[maxn];

void solve( ) {
    int n = read( ), m = read( );
    dsu.init( n );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ) + 1, v = read( ) + 1;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    int k = read( );
    for( int i = 1; i <= k; ++ i ) {
        ks[i] = read( ) + 1;
        broken[ks[i]] = true;
    }

    int cnt = n - k; // 连通块数量
    for( int u = 1; u <= n; ++ u ) {
        if( broken[u] ) continue;
        for( int v : adj[u] ) {
            if( broken[v] ) continue;
            if( dsu.merge( u, v ) ) cnt --;
        }
    }

    ans[k + 1] = cnt;
    for( int i = k; i >= 1; -- i ) {
        int u = ks[i];
        broken[u] = 0;
        cnt ++;
        for( int v : adj[u] ) {
            if( broken[v] ) continue;
            if( dsu.merge( u, v ) ) cnt --; // 尝试恢复 u 的相邻边
        }
        ans[i] = cnt; // 恢复 u 后的连通块数量
    }

    for( int i = 1; i <= k + 1; ++ i ) {
        cout << ans[i] << '\n';
    }
}

二、扩展域模型

扩展域模型适合处理「同类 / 异类」「敌人 / 朋友」「吃 / 被吃」这类离散关系。

它的核心是：给每个点拆出若干个离散域，然后把关系转化为连通性，若某个点和它不改相同的域连通，就说明存在矛盾。

二倍域模板

适用于只有两种相对关系的题，比如同类 / 异类、朋友 / 敌人、二分图两侧。

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
// 二倍域并查集：维护同类 / 异类
struct ExtDSU {
/* ======================================== */
int fa[maxn << 1], siz[maxn << 1], sz;
void init( int N ) { 
    sz = N; 
    for( int i = 1; i <= (N << 1); ++ i ) fa[i] = i, siz[i] = 1;
}
int rev( int x ) { return x <= sz ? x + sz : x - sz; }
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 )]; }
bool setSame( int x, int y ) {
    if( same( x, rev( y ) ) ) return 0;
    merge( x, y ), merge( rev( x ), rev( y ) );
    return 1;
}
bool setDiff( int x, int y ) {
    if( same( x, y ) ) return 0;
    merge( x, rev( y ) ), merge( rev( x ), y );
    return 1;
}
/* ======================================== */
} dsu;

三倍域模板

适用于三元循环关系，比如食物链中的同类、吃、被吃。

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
// 三倍域并查集：维护同类 / 吃 / 被吃
struct ExtDSU {
/* ======================================== */
int fa[maxn * 3], siz[maxn * 3], sz;
void init( int N ) { 
    sz = N; 
    for( int i = 1; i <= (N * 3); ++ i ) fa[i] = i, siz[i] = 1;
}
int id( int x, int k ) { return x + k * sz; }
// k = 0: x 自己 | k = 1: x 吃谁 | k = 2: x 被谁吃
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 )]; }
bool setSame( int x, int y ) {
    if( same( id(x, 0), id(y, 1) ) ) return 0;
    if( same( id(x, 0), id(y, 2) ) ) return 0;
    merge( id(x, 0), id(y, 0) );
    merge( id(x, 1), id(y, 1) );
    merge( id(x, 2), id(y, 2) );
    return 1;
}
bool setEat( int x, int y ) {
    if( same( id(x, 0), id(y, 0) ) ) return 0;
    if( same( id(x, 0), id(y, 1) ) ) return 0;
    merge( id(x, 0), id(y, 2) );
    merge( id(x, 1), id(y, 0) );
    merge( id(x, 2), id(y, 1) );
    return 1;
}
/* ======================================== */
} dsu;

4. P1892 [BOI2003] 团伙

题意

有 nn 个人和 mm 条关系。F p q 表示 p,qp, q 是朋友；E p q 表示 p,qp, q 是敌人。敌人的敌人是朋友，问最后有多少个团伙。

思路

这题不能用二倍域的做法，因为朋友的朋友是朋友，敌人的敌人是朋友，但是敌人的朋友不一定是敌人，这里采用 enemy[] 标记法，只维护题目要求的关系：

  • 如果 p,qp, q 是朋友，直接合并。
  • 如果 p,qp, q 是敌人，那么 pp 的敌人应该和 qq 合并，qq 的敌人应该和 pp 合并。

因为最后只问团伙数量，所以枚举连通块数目即可。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e3 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct DSU { /* 板子略 */ } dsu;
/* ============================== */

int enemy[maxn];

void solve( ) {
    int n = read( ), m = read( );
    dsu.init( n );
    for( int i = 1; i <= m; ++ i ) {
        char opt; cin >> opt;
        int p = read( ), q = read( );
        if( opt == 'F' ) dsu.merge( p, q );
        else {
            if( enemy[p] ) dsu.merge( enemy[p], q );
            else enemy[p] = q;
            if( enemy[q] ) dsu.merge( enemy[q], p );
            else enemy[q] = p;
        }
    }
    
    int cnt = 0;
    for( int i = 1; i <= n; ++ i ) {
        if( dsu.find( i ) == i ) ++ cnt;
    }
    cout << cnt << '\n';
}

int main( ) {
    solve( );
    return 0;
}

5. P1525 [NOIP2010] 关押罪犯

题意

有两个监狱，给定若干对罪犯之间的仇恨值。需要安排每个罪犯所在的监狱，使得同一个监狱内冲突值最大的那一对尽可能小。

思路

这题的核心是「先保证大的冲突尽量不发生」。

把所有冲突按照权值从大到小排序，依次处理。对于当前冲突 (a,b,c)(a,b,c)，如果还想让答案小于 cc，就必须让 a,ba,b 分到不同监狱。

因此可以把每个人拆成两个域：x 表示 xx 所在阵营，rev(x) 表示 xx 的对立阵营，要求 a,ba,b 不同，就等价于：

1
2
merge( a, rev( b ) );
merge( rev( a ), b );

如果加入这条「不同」约束前，发现 a,ba,b 已经在同一个集合里，就说明权值为 cc 的冲突无法再避免，答案就是 cc。

这题本质上是在按边权从大到小维护一个二分图判定，只是用二倍域并查集替代染色过程。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e4 + 5;
const int maxm = 1e5 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct ExtDSU { /* 二倍域板子略 */ } dsu;
/* ============================== */

struct Person {
    int a, b, c;
    bool operator < ( const Person &oth ) const { return c > oth.c; }
} p[maxm];

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        p[i].a = read( ), p[i].b = read( ), p[i].c = read( );
    }
    sort( p + 1, p + m + 1 );

    dsu.init( n );
    for( int i = 1; i <= m; ++ i ) {
        auto [ai, bi, ci] = p[i];
        if( !dsu.setDiff( ai, bi ) ) {
            cout << ci << '\n';
            return;
        }
    }
    cout << 0 << '\n';
}

6. P2024 [NOI2001] 食物链：三倍域写法

题意

有三类动物构成循环捕食关系。给定若干句话：1 x y 表示 x,yx,y 同类，2 x y 表示 xx 吃 yy，问有多少句话是假话。

思路

食物链关系不是简单的同类 / 异类，而是一个长度为 33 的循环关系，所以可以把每个动物拆成三个域：

  • id(x, 0)：xx 自己所在的类。
  • id(x, 1)：xx 吃的那一类。
  • id(x, 2)：吃 xx 的那一类。

如果 x,yx,y 同类，那么它们的三层关系都应该对应相同：

1
2
3
merge( id( x, 0 ), id( y, 0 ) );
merge( id( x, 1 ), id( y, 1 ) );
merge( id( x, 2 ), id( y, 2 ) );

如果 xx 吃 yy，那么 xx 自己这一类等于吃 yy 的那一类，xx 吃的那一类等于 yy 自己这一类，吃 xx 的那一类等于 yy 吃的那一类：

1
2
3
merge( id( x, 0 ), id( y, 2 ) );
merge( id( x, 1 ), id( y, 0 ) );
merge( id( x, 2 ), id( y, 1 ) );

加入关系前先判断是否矛盾；如果 x,yx,y 超出动物编号范围，也直接判为假话。

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e4 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct ExtDSU { /* 三倍域板子略 */ } dsu;
/* ============================== */

void solve( ) {
    int n = read( ), k = read( );
    dsu.init( n );

    int ans = 0;
    for( int i = 1; i <= k; ++ i ) {
        int opt = read( ), x = read( ), y = read( );
        if( x > n || y > n ) ans ++;
        else if( opt == 1 && !dsu.setSame( x, y ) ) ans ++;
        else if( opt == 2 && !dsu.setEat( x, y ) ) ans ++;
    }
    cout << ans << '\n';
}

三、带权并查集

带权并查集适合维护「点与点之间的相对关系」。它不再只是问两个点是否连通，还能在连通时查询 val[x]−val[y]val[x] - val[y]。

常见两种版本：

  1. 取模带权并查集：维护 (val[x]−val[y]) mod mod(val[x] - val[y]) \bmod mod，适合循环关系，比如食物链。
  2. 势能差带权并查集：维护真实差值 val[x]−val[y]val[x] - val[y]，适合前缀和、距离、区间和一类差分约束。

带权并查集模板：取模

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

// 带权并查集：维护 (val[x] - val[y]) mod mod
struct WDSU {
/* ======================================== */
static const int mod = 3;
int fa[maxn], siz[maxn], dis[maxn]; // dis[x] = val[x] - val[fa[x]] (mod mod)
int norm( int x ) { return ( x %= mod ) < 0 ? x + mod : x; }
void init( int N ) {
    for( int i = 1; i <= N; ++ i ) fa[i] = i, siz[i] = 1, dis[i] = 0;
}
int find( int x ) {
    if( fa[x] == x ) return x;
    int f = fa[x];
    fa[x] = find( f );
    dis[x] = norm( dis[x] + dis[f] );
    return fa[x];
}
// 查询 (val[x] - val[y]) mod mod，调用前最好保证 same(x, y)
int dist( int x, int y ) {
    find( x ), find( y );
    return norm( dis[x] - dis[y] );
}
// 加入关系 val[x] - val[y] = w (mod mod)，返回 false 表示矛盾
bool merge( int x, int y, int w ) {
    w = norm( w );
    int rx = find( x ), ry = find( y );
    if( rx == ry ) return dist( x, y ) == w;
    if( siz[rx] > siz[ry] ) {
        fa[ry] = rx;
        dis[ry] = norm( -w + dis[x] - dis[y] );
        siz[rx] += siz[ry];
    } else {
        fa[rx] = ry;
        dis[rx] = norm( w - dis[x] + dis[y] );
        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;

带权并查集模板：势能差

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;

// 带权并查集：维护 val[x] - val[y]，不取模
struct WDSU {
/* ======================================== */
int fa[maxn], siz[maxn];
ll dis[maxn]; // dis[x] = val[x] - val[fa[x]]
void init( int N ) {
    for( int i = 1; i <= N; ++ i ) fa[i] = i, siz[i] = 1, dis[i] = 0;
}
int find( int x ) {
    if( fa[x] == x ) return x;
    int f = fa[x];
    fa[x] = find( f );
    dis[x] += dis[f];
    return fa[x];
}
// 查询 val[x] - val[y]，调用前最好保证 same(x, y)
ll dist( int x, int y ) {
    find( x ), find( y );
    return dis[x] - dis[y];
}
// 加入关系 val[x] - val[y] = w，返回 false 表示矛盾
bool merge( int x, int y, ll w ) {
    int rx = find( x ), ry = find( y );
    if( rx == ry ) return dist( x, y ) == w;
    if( siz[rx] > siz[ry] ) {
        fa[ry] = rx;
        dis[ry] = -w + dis[x] - dis[y];
        siz[rx] += siz[ry];
    } else {
        fa[rx] = ry;
        dis[rx] = w - dis[x] + dis[y];
        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;

7. P2024 [NOI2001] 食物链：带权写法

题意

同上一题，判断食物链中有多少句假话。

思路

三倍域是把每个点拆成三个域；带权并查集则是把这三种关系压成一个模 33 意义下的差值。

令 dist(x, y) = (val[x] - val[y]) mod 3，那么：

  • dist(x, y) = 0：x,yx,y 同类。
  • dist(x, y) = 1：xx 吃 yy。
  • dist(x, y) = 2：xx 被 yy 吃。

所以 opt == 1 就是加入 val[x] - val[y] = 0，opt == 2 就是加入 val[x] - val[y] = 1。

带权并查集的 merge(x, y, w) 本身就可以处理两种情况：如果 x,yx,y 已经连通，就检查原有差值是否等于 ww；如果还不连通，就合并两个集合，并维护新根到旧根之间的差值。

从复习角度看，这个写法比三倍域更抽象，但代码更短，也更接近「关系 = 差值约束」这个本质。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e4 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct WDSU { /* 带权取模板子略 */ } dsu;
/* ============================== */

void solve( ) {
    int n = read( ), k = read( );
    dsu.init( n );
    int ans = 0;
    for( int i = 1; i <= k; ++ i ) {
        int opt = read( ), x = read( ), y = read( );
        if( x > n || y > n ) ans ++;
        else if( opt == 1 ) {
            if( dsu.same( x, y ) && dsu.dist( x, y ) != 0 ) ans ++;
            else dsu.merge( x, y, 0 );
        }
        else if( opt == 2 ) {
            if( dsu.same( x, y ) && dsu.dist( x, y ) != 1 ) ans ++;
            else dsu.merge( x, y, 1 );
        }
    }
    cout << ans << '\n';
}

8. P2294 [HNOI2005] 狡猾的商人

题意

给定若干区间和约束：区间 [l,r][l,r] 的和为 ss。判断这些信息是否自洽。

思路

这题看上去是区间信息，实际上可以转成前缀和之间的差值关系。

设 pre[i]pre[i] 表示前 ii 项的和，那么区间 [l,r][l,r] 的和为：

pre[r]−pre[l−1]=spre[r] - pre[l - 1] = s

这正好是势能差并查集维护的形式：val[r] - val[l - 1] = s。

如果 rr 和 l−1l - 1 已经连通，就检查当前维护出的差值是否等于 ss；如果还不连通，就把这条差值约束加入并查集。

注意这里会用到点 00，所以初始化时需要包含 0∼n0 \sim n。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct WDSU { /* 势能差板子略，init 需要包含 0 */ } dsu;
/* ============================== */

void solve( ) {
    int n = read( ), m = read( );
    dsu.init( n );

    bool ok = 1;
    for( int i = 1; i <= m; ++ i ) {
        int l = read( ), r = read( ), s = read( );
        if( !dsu.merge( r, l - 1, s ) ) ok = 0;
    }

    cout << ( ok ? "true" : "false" ) << '\n';
}

int main( ) {
    int _ = read( );
    while( _ -- ) solve( );
    return 0;
}

四、队列模型

队列模型也是带权思想的一种特殊应用，但它维护的不是抽象关系，而是队列中的真实位置。

这里的 dis[x] 表示 xx 到所在队列队头的距离。把 x 所在整列接到 y 所在整列后面时，设 rx = find(x), ry = find(y)，就有：

1
2
3
fa[rx] = ry;
dis[rx] = siz[ry];
siz[ry] += siz[rx];

路径压缩时累加 dis[x] += dis[f]，就能维护每个点到当前队头的距离。注意这个模型不能按 连通块大小 进行合并，因为合并方向本身有意义：必须是「xx 所在整列接到 yy 所在整列后面」。

队列合并模板

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;

// 队列合并并查集：整列接到整列后面，维护到队头距离
struct QDSU {
/* ======================================== */
int fa[maxn], siz[maxn];
ll dis[maxn]; // dis[x] = x 到所在列队头的距离
void init( int N ) { for( int i = 1; i <= N; ++ i ) fa[i] = i, siz[i] = 1, dis[i] = 0; }
int find( int x ) {
    if( fa[x] == x ) return x;
    int f = fa[x];
    fa[x] = find( fa[x] );
    dis[x] += dis[f];
    return fa[x];
}
// 把 x 所在整列接到 y 所在整列后面
void move( int x, int y ) {
    int rx = find( x ), ry = find( y );
    if( rx == ry ) return;
    fa[rx] = ry;
    dis[rx] = siz[ry];
    siz[ry] += siz[rx];
}
bool same( int x, int y ) { return find( x ) == find( y ); }
int size( int x ) { return siz[find( x )]; }
// x 到队头的距离
ll pos( int x ) {
    find( x );
    return dis[x];
}
// x, y 之间隔了几个元素；调用前需保证 same(x, y)
ll dist( int x, int y ) {
    find( x ), find( y );
    return abs( dis[x] - dis[y] ) - 1;
}
/* ======================================== */
} dsu;

9. P1196 [NOI2002] 银河英雄传说

题意

一开始每艘战舰单独成列。M x y 表示把 xx 所在整列接到 yy 所在整列后面；C x y 询问 x,yx,y 是否在同一列，如果在同一列，输出它们之间隔了多少艘战舰，否则输出 -1。

思路

这题的关键不是普通合并，而是「整列接到整列后面」。

用 siz[rt] 维护每一列的长度，dis[x] 维护 xx 到当前队头的距离。

当执行 M x y 时，设 rx = find(x), ry = find(y)，要把 xx 所在整列接到 yy 所在整列后面，所以：

1
2
3
fa[rx] = ry;
dis[rx] = siz[ry];
siz[ry] += siz[rx];

查询时，如果 x,yx,y 不在同一列，输出 -1；否则两者之间隔着的战舰数就是：

1
abs( dis[x] - dis[y] ) - 1

这里 find 的路径压缩会顺手累加距离，所以查询前调用 find(x), find(y) 后，dis[] 就是到当前队头的真实距离。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e4 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct QDSU { /* 队列合并板子略 */ } dsu;
/* ============================== */

void solve( ) {
    int T = read( );
    dsu.init( maxn - 1 );

    for( int i = 1; i <= T; ++ i ) {
        char opt;
        cin >> opt;
        int x = read( ), y = read( );
        if( opt == 'M' ) {
            dsu.move( x, y );
        }
        if( opt == 'C' ) {
            if( !dsu.same( x, y ) ) cout << -1 << '\n';
            else cout << dsu.dist( x, y ) << '\n';
        }
    }
}

10. P5092 [USACO04OPEN] Cube Stacking

题意

维护若干队列。支持把 xx 所在整列接到 yy 所在整列后面，并查询某个元素 xx 到所在队列队头的距离。

思路

这题和 P1196 用的是同一个队列合并模型，只是询问更简单。

P1196 查询的是两个点之间隔了多少元素，所以要用：

1
dist( x, y ) = abs( dis[x] - dis[y] ) - 1

而这题查询的是单点 xx 到队头的距离，因此路径压缩后直接输出：

1
pos( x ) = dis[x]

所以这题可以看作队列合并模板中 pos(x) 的直接应用。

代码部分

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;

/* ============================== */
ll read( ) { /* 板子略 */ }
struct QDSU { /* 队列合并板子略 */ } dsu;
/* ============================== */

void solve( ) {
    int n = read( );
    dsu.init( n );

    for( int i = 1; i <= n; ++ i ) {
        char opt;
        cin >> opt;
        if( opt == 'M' ) {
            int x = read( ), y = read( );
            dsu.move( x, y );
        }
        if( opt == 'C' ) {
            int x = read( );
            cout << dsu.pos( x ) << '\n';
        }
    }
}
笔记 > 并查集
#数据结构/并查集
[Solution] 并查集题型整理
http://miqiu.space/posts/f753ba00/
作者
Miqiu
发布于
2026年6月4日
许可协议