并查集典型应用

一、连通性问题

连通性问题是并查集最基本也是最常见的应用场景。在这类问题中，我们需要判断图中的两个节点是否连通，或者维护图的连通性信息。

1.1 判断两点是否连通

最简单的连通性问题是判断两个节点是否连通。使用并查集，我们可以通过查找两个节点是否属于同一个集合来判断它们是否连通。

// 判断节点x和y是否连通
bool isConnected(int x, int y) {
    return find(x) == find(y);
}

示例：洛谷P1551 亲戚

规定：$x$ 和 $y$ 是亲戚，$y$ 和 $z$ 是亲戚，那么 $x$ 和 $z$ 也是亲戚。如果 $x$，$y$ 是亲戚，那么 $x$ 的亲戚都是 $y$ 的亲戚，$y$ 的亲戚也都是 $x$ 的亲戚。

输入数据格式

第一行：三个整数 $n,m,p$，（$n,m,p \le 5000$），分别表示有 $n$ 个人，$m$ 个亲戚关系，询问 $p$ 对亲戚关系。

以下 $m$ 行：每行两个数 $M_i$，$M_j$，$1 \le M_i,~M_j\le n$，表示 $M_i$ 和 $M_j$ 具有亲戚关系。

接下来 $p$ 行：每行两个数 $P_i,P_j$，询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。

输出数据格式

$p$ 行，每行一个 Yes 或 No。表示第 $i$ 个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例

输入 #1	输出 #1
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6	Yes Yes No

这道题目要求判断两个人是否有亲戚关系，可以直接使用并查集解决：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
int parent[MAXN];

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void unionSets(int x, int y) {
    parent[find(x)] = find(y);
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    // 合并亲戚关系
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        unionSets(x, y);
    }
    
    // 查询
    for (int i = 0; i < p; i++) {
        int x, y;
        cin >> x >> y;
        if (find(x) == find(y)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;
}

1.2 动态连通性维护

动态连通性问题是指在图中不断添加边，并查询两点是否连通的问题。并查集可以高效地维护这种动态变化的连通性信息。

示例：村村通

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入数据格式

输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 $n$ 和道路数目 $m$ ；随后的 $m$ 行对应 $m$ 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 $1$ 到 $n$ 编号。

注意：两个城市间可以有多条道路相通。

在输入数据的最后，为一行一个整数 $0$，代表测试数据的结尾。

输出数据格式

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

输入输出样例

输入 #1	输出 #1
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0	1 0 2 998

这道题目要求计算需要修建的最少道路数量，使得所有村庄都连通。这实际上是求连通分量的数量减一：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int parent[MAXN];

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void unionSets(int x, int y) {
    parent[find(x)] = find(y);
}

int main() {
    int n, m;
    while (cin >> n && n != 0) {
        cin >> m;
        
        // 初始化
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        // 合并已有道路连接的村庄
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            unionSets(x, y);
        }
        
        // 计算连通分量数量
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i) {
                count++;
            }
        }
        
        // 需要修建的道路数量 = 连通分量数量 - 1
        cout << count - 1 << endl;
    }
    
    return 0;
}

二、等价类划分

并查集可以用于将具有等价关系的元素划分到同一组。等价关系满足自反性、对称性和传递性。

2.1 集合的合并与查询(示例：团伙)

在等价类划分问题中，我们通常需要处理两种操作：

1. 合并两个等价类
2. 查询两个元素是否属于同一等价类

现在有 $n$ 个人，他们之间有两种关系：朋友和敌人。我们知道：

• 一个人的朋友的朋友是朋友
• 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入数据格式

第一行输入一个整数 $n$ 代表人数。

第二行输入一个整数 $m$ 表示接下来要列出 $m$ 个关系。

接下来 $m$ 行，每行一个字符 $opt$ 和两个整数 $p,q$，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 $opt$ 有两种可能：

• 如果 $opt$ 为 F，则表明 $p$ 和 $q$ 是朋友。
• 如果 $opt$ 为 E，则表明 $p$ 和 $q$ 是敌人。

输出数据格式

一行一个整数代表最多的团体数。

输入输出样例

输入 #1	输出 #1
6 4 E 1 4 F 3 5 F 4 6 E 1 2	3

说明与提示

对于 $100\%$ 的数据，$2 \le n \le 1000$，$1 \le m \le 5000$，$1 \le p,q \le n$。

这道题目涉及到敌人的敌人是朋友的关系，可以使用并查集维护朋友关系：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int parent[MAXN];
vector<int> enemy[MAXN];  // 记录每个人的敌人

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void unionSets(int x, int y) {
    parent[find(x)] = find(y);
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    // 处理关系
    for (int i = 0; i < m; i++) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        
        if (op == 'F') {
            // 朋友关系，直接合并
            unionSets(a, b);
        } else {
            // 敌人关系，记录下来
            enemy[a].push_back(b);
            enemy[b].push_back(a);
        }
    }
    
    // 敌人的敌人是朋友
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < enemy[i].size(); j++) {
            for (int k = j + 1; k < enemy[i].size(); k++) {
                unionSets(enemy[i][j], enemy[i][k]);
            }
        }
    }
    
    // 计算团伙数量
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (parent[i] == i) {
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;
}

三、最小生成树问题

并查集在最小生成树算法中有重要应用，特别是在Kruskal算法中，用于判断添加一条边是否会形成环。

3.1 Kruskal算法中的应用(示例：【模板】最小生成树)

克鲁斯卡尔算法（Kruskal） 是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 再按边权从小到大遍历所有边，如果当前边连接的两个顶点不在同一个连通分量中，则将这条边加入最小生成树。并查集用于判断两个顶点是否在同一个连通分量中。

给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入数据格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出数据格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1	输出 #1
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3	7

这是一道最小生成树的模板题，可以使用Kruskal算法(克鲁斯卡尔算法)结合并查集解决：

Kruskal算法求最小生成树

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
int parent[MAXN];

struct Edge {
    int u, v, w;
    // 移除操作符重载
};

// 自定义比较函数：按边权升序排列
bool compareEdges(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void unionSets(int x, int y) {
    parent[find(x)] = find(y);
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    
    // 使用自定义比较函数排序
    sort(edges.begin(), edges.end(), compareEdges);
    
    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    int totalWeight = 0;
    int edgeCount = 0;
    
    for (const Edge& e : edges) {
        int u = e.u, v = e.v, w = e.w;
        
        if (find(u) != find(v)) {
            unionSets(u, v);
            totalWeight += w;
            edgeCount++;
            
            if (edgeCount == n - 1) {
                break;
            }
        }
    }
    
    if (edgeCount == n - 1) {
        cout << totalWeight << endl;
    } else {
        cout << "orz" << endl;
    }
    
    return 0;
}

四、带权并查集

带权并查集是并查集的一种扩展，它不仅维护元素所属的集合，还维护元素之间的某种关系（通常是权值或距离）。

概念与实现

在带权并查集中，除了记录每个元素的父节点外，还需要记录元素到其父节点的权值。这个权值可以表示距离、差值或其他任何可以进行运算的量。

基本实现思路：

const int MAXN = 10005;
int parent[MAXN];
int weight[MAXN];  // 记录到父节点的权值

// 初始化
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        weight[i] = 0;  // 初始权值为0
    }
}

// 带权查找
int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    
    int root = find(parent[x]);
    weight[x] += weight[parent[x]];  // 更新权值
    parent[x] = root;  // 路径压缩
    return root;
}

// 带权合并
void unionSets(int x, int y, int w) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
        parent[rootX] = rootY;
        weight[rootX] = weight[y] - weight[x] + w;  // 更新权值
    }
}

应用场景

带权并查集常用于解决以下类型的问题：

1. 食物链问题：维护动物之间的捕食关系
2. 相对大小问题：维护元素之间的大小关系
3. 距离问题：维护元素之间的距离关系

示例：银河英雄传说

这道题目要求维护舰队之间的相对位置关系，可以使用带权并查集解决：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;
int parent[MAXN];
int size[MAXN];    // 记录集合大小
int distance[MAXN]; // 记录到根节点的距离

int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    
    int root = find(parent[x]);
    distance[x] += distance[parent[x]];  // 更新距离
    parent[x] = root;  // 路径压缩
    return root;
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
        parent[rootX] = rootY;
        distance[rootX] = size[rootY];  // 更新距离
        size[rootY] += size[rootX];     // 更新集合大小
    }
}

int main() {
    int t;
    cin >> t;
    
    // 初始化
    for (int i = 1; i < MAXN; i++) {
        parent[i] = i;
        size[i] = 1;
        distance[i] = 0;
    }
    
    while (t--) {
        char op;
        int i, j;
        cin >> op >> i >> j;
        
        if (op == 'M') {
            unionSets(i, j);
        } else {
            if (find(i) != find(j)) {
                cout << -1 << endl;
            } else {
                cout << abs(distance[i] - distance[j]) - 1 << endl;
            }
        }
    }
    
    return 0;
}

扩展练习：

1. 村村通
2. 亲戚
3. [BOI2003] 团伙
4. 最小生成树
5. 修复公路
6. [NOI2002] 银河英雄传说
7. [NOIP2010 提高组] 关押罪犯
8. [NOI2001] 食物链

*学习笔记

暂没有学习笔记，快来抢first blood ！