带权并查集

续前章节：并查集及应用

1 带权问题

1.1 点带权

用num[i]记录节点 $i$ 所在的集合的数量。

初始化：所有的num[i]都是 $1$ ，因为每个点 $i$ 都是自成一个集合。

我们只能在add()和find()中更新和维护num[]。

add()：

void add(int x, int y) {
    int xx = find(x);
    int yy = find(y);
    if (xx != yy) 
        fa[xx] = yy, num[yy] += num[xx];
    //x所在集合合并到y所在的集合，所以y所在集合的节点个数应该加上x所在集合的节点个数
}

find()：不做改动。

注意：仅仅每个集合的根节点 $i$ 的num[i]具有时效性和真实性。一个集合里除根节点以外的其他节点的num[i]时滞后的，没有意义。也就是说，在一个点所在集合的点的数量保存在其根节点的num[]中。

1.2 边带权

用dis[i]记录节点 $i$ 到所在集合的根节点的距离（边权是 $1$ ）。

初始化：全部是 $0$ ，因为每个点自为一个集合，自己到自己的距离是 $0$ 。

add()：

void add(int x, int y) {
    int xx = find(x);
    int yy = find(y);
    if (xx != yy) 
        fa[xx] = yy, dis[x] = dis[y] + 1;
    //理论上来讲，是x成为了y的子节点，所以x和y之间多了一条边，而且现在的dis[x]应当是到y所在集合根节点的距离
    //原先x所在集合的其他节点的dis[]会在find()中更新
}

find()：每次find()过程中把集合更新维护一遍。

int find(int x) {
    if (fa[x] == x)
        return x;
    int k = find(fa[x]);
    //在x更新之前，先把它的所有祖先节点更新了
    dis[x] += dis[fa[x]];
    //换了新的根节点后，合并进来的集合中的每个节点都应当再加上一个距离(原根节点到新根节点的距离)，从fa[x]依次向下更新
    return fa[x] = k;
}

注意：因为真正把一整个集合重新更新dis[]以来find()函数，所以在每次获取dis[i]的值之前，应当先把 $i$ 所在集合find()一遍。

2 例题

2.1 家族合并

题目描述

有 n 个人，刚开始每个人都代表着一个家族，现在要对其进行 $Q$ 次操作，一共有如下三种操作：

C a b，a 和 b 所在的家族合并到一起
Q1 a b，查询 a 和 b 是否在同一个家族
Q2 a，查询 a 所在的家族有多少个人

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个家族中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在家族的人数。

题解

点带权问题。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, a, b, fa[N], num[N];
string s;
int find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void add(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) 
        fa[x] = y, num[y] += num[x];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        fa[i] = i, num[i] = 1;
    while (m--) {
        cin >> s;
        if (s == "C") {
            cin >> a >> b;
            add(b, a);
        } else if (s == "Q1") {
            cin >> a >> b;
            if (find(a) == find(b))
                cout << "Yes" << endl;
            else   
                cout << "No" << endl;
        } else {
            cin >> a;
            cout << num[find(a)] << endl;
        }
    }
    return 0;
}

2.2 信息传递

题目描述

$n$ 名同学，每名同学都有一个固定的传递对象（非本人，一个人可能同为多个人的传递对象）。每个人都有一条自己特有的信息。

每进行一轮游戏时，每个人都会把自己已知的所有信息告诉传递对象，同时接收别人传来的信息。当有一个人从别人那里接收到自己的信息时，游戏停止。

问游戏可以进行几轮。

题解

每名同学都有一个固定的传递对象（非本人……

这句话告诉我们： $n$ 名同学必然会形成一个环。

也就是说：当环里的一名同学的信息在环中传递了一遍，最后又传到自己时，游戏就停止了。这个环一定是最小的环。

现在问题转化为：求最小的一个环有多少个节点（或者多少条边）组成。因为不是所有的num[]都是最新的，考虑求边数。

什么时候会产生环？

在并查集中，如果两个节点已经在同一个集合中，这两个点还要建立关系，就会形成环。

可以发现，一个环里如果信息能够顺畅传递，必然含有根节点。

在一个集合里，环通常是这样的：

集合中的环

也就是说，知道知道一个环里有 $x, y$ 这两个节点，这个环的边数必然等于 dis[x] + dis[y] + 1（以上图为例， $y$ 到根节点的距离 $2$ 加上 $x$ 到根节点的距离 $2$ ，加上 $x, y$ 之间的距离 $1$ ，环的总边数为 $5$ ）。

每次发现环时，堆环的边数求最小值即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, fa[N], dis[N], ans = INT_MAX, a;
string s;
int find(int x) {
    if (fa[x] == x)
        return x;
    dis[x] += dis[fa[x]];
    return fa[x] = find(fa[x]);
}
void add(int x, int y) {
    int x2 = find(x);
    int y2 = find(y);
    if (x2 == y2) 
        ans = min(ans, dis[x] + dis[y] + 1);  //发现环，记录答案
    fa[x2] = y2;
    dis[x] = dis[y] + 1;
}
int main() {
    CLOSE;
    cin >> n;
    for (int i = 1; i <= n; i++) 
        fa[i] = i;
    for (int i = 1; i <= n; i++) 
        cin >> a, add(i, a); //注意i和a的顺序
    cout << ans;
    return 0;
}

2.3 [NOI2002] 银河英雄传说

P1196 [NOI2002] 银河英雄传说 - 洛谷

题目描述

敌军将战场划分为 $30000$ 列，开战之前，将序号为 $1,2,3,\dots,30000$ 的战舰依次放置到对应的列上。

在战斗中，敌军会对战舰发出合并指令：

M i j：表示 $i$ 号战舰所在一整列的战舰作为一个整体（头在前尾在后）接在 $j$ 号战舰所在列的尾部。

我军的系统监听到了敌军的这些指令。我军指挥官会随时向系统发出询问指令：

C i j：询问 $i$ 号战舰和 $j$ 号战舰之间隔着多少战舰。如果 $i$ 和 $j$ 号军舰，不在同一列，输出 -1。

现在请处理我军和敌军所有的 $T$ 条指令。

题解

因为所有节点成链状，不妨考虑点、边权结合。

find()函数和边带权一样。

add()函数：

void add(int x, int y) {
    int xx = find(x);
    int yy = find(y);
    if (xx == yy) return;
    fa[xx] = yy;
    dis[xx] = num[yy];//根节点xx接在yy所在集合的尾部后面，到根节点yy的距离显然就是原先yy集合的节点数
    num[yy] += num[xx];  //yy集合的节点数加上加入的xx集合的数量
}

再看主函数部分：

int main() {
    CLOSE;
    cin >> m;
    for (int i = 1; i <= 3e4 + 10; i++)
        fa[i] = i, num[i] = 1;
    while (m--) {
        int x, y;
        cin >> s >> x >> y;
        if (s == "M") {
            add(x, y); //注意x和y的顺序
        } else {
            int k1 = find(x), k2 = find(y);  //先find()一下，更新dis[]
            if (k1 != k2) 
                cout << -1 << endl;
            else 
                cout << (int)(abs(dis[x] - dis[y])) - 1 << endl;
            //不确定x和y的先后，取绝对值
        }
    }
    return 0;
}