当前位置：首页 > news >正文

C++并查集实战：从Wireless_Network到关押罪犯的5个经典问题解析

news 2026/6/24 20:45:06

C++并查集实战：从Wireless_Network到关押罪犯的5个经典问题解析

在算法竞赛中，并查集（Disjoint Set Union，DSU）是一种高效处理不相交集合合并与查询问题的数据结构。它以其简洁的实现和近乎常数的操作时间复杂度，成为解决连通性问题的利器。本文将深入解析5个经典竞赛题目，从基础应用到高级技巧，帮助C++开发者掌握并查集的实战应用。

1. 基础并查集：Wireless_Network问题

Wireless_Network是POJ上经典的并查集入门题，题目描述了一系列计算机在特定距离内可以通信，要求判断两台计算机是否能够直接或间接通信。

#include <vector> #include <cmath> using namespace std; struct Point { double x, y; }; vector<int> parent; vector<Point> computers; void init(int n) { parent.resize(n); for(int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void merge(int a, int b) { int fa = find(a), fb = find(b); if(fa != fb) parent[fa] = fb; } bool canCommunicate(int a, int b, double d) { double dx = computers[a].x - computers[b].x; double dy = computers[a].y - computers[b].y; return dx*dx + dy*dy <= d*d; }

关键优化点：

使用路径压缩的find函数，确保查询效率
预处理所有计算机之间的距离关系
在修复计算机时动态更新连通关系

提示：在实际竞赛中，浮点数比较可能存在精度问题，可以转换为整数运算避免误差。

2. 带权并查集：The_Suspects计数应用

The_Suspects问题需要统计与0号病人同组的病人数量，展示了带权并查集在计数方面的应用。

vector<int> parent, size; void init(int n) { parent.resize(n); size.resize(n, 1); for(int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void merge(int a, int b) { int fa = find(a), fb = find(b); if(fa != fb) { parent[fa] = fb; size[fb] += size[fa]; } } int countSuspects() { return size[find(0)]; }

实现要点：

size数组维护每个集合的大小
合并时更新集合大小
查询0号所在集合的大小即可得到结果

3. 种类并查集：关押罪犯问题

关押罪犯问题需要将罪犯分成两组，使同一组内的冲突值最小，展示了种类并查集的典型应用。

vector<int> parent; void init(int n) { parent.resize(2 * n); for(int i = 0; i < 2 * n; ++i) parent[i] = i; } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void merge(int a, int b) { parent[find(a)] = find(b); } bool isConflict(int a, int b) { return find(a) == find(b); } void addEnemy(int a, int b) { merge(a, b + n); merge(b, a + n); }

二进制思路解析：

每个元素有两个状态：A组或B组
使用i表示在A组，i+n表示在B组
敌人的敌人是朋友，通过这种关系建立连接

4. 食物链问题：三态种类并查集

食物链问题是种类并查集的经典扩展，需要处理三种生物之间的捕食关系。

vector<int> parent, relation; void init(int n) { parent.resize(n); relation.resize(n, 0); for(int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { if(parent[x] != x) { int old = parent[x]; parent[x] = find(parent[x]); relation[x] = (relation[x] + relation[old]) % 3; } return parent[x]; } bool unionSet(int a, int b, int r) { int fa = find(a), fb = find(b); if(fa == fb) { return (relation[a] - relation[b] + 3) % 3 == r; } parent[fa] = fb; relation[fa] = (relation[b] - relation[a] + r + 3) % 3; return true; }

关系传递分析：

0: 同类
1: a吃b
2: b吃a
关系通过模3运算保持一致性

5. 高级应用：银河英雄传说

银河英雄传说问题需要维护战舰之间的前后关系，展示了带权并查集在距离计算中的应用。

vector<int> parent, rank, dist; void init(int n) { parent.resize(n); rank.resize(n, 1); dist.resize(n, 0); for(int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { if(parent[x] != x) { int root = find(parent[x]); dist[x] += dist[parent[x]]; parent[x] = root; } return parent[x]; } void merge(int a, int b) { int fa = find(a), fb = find(b); if(fa != fb) { parent[fa] = fb; dist[fa] = rank[fb]; rank[fb] += rank[fa]; } } int query(int a, int b) { if(find(a) != find(b)) return -1; return abs(dist[a] - dist[b]) - 1; }

距离维护技巧：