C并查集实战从Wireless_Network到关押罪犯的5个经典问题解析在算法竞赛中并查集Disjoint Set UnionDSU是一种高效处理不相交集合合并与查询问题的数据结构。它以其简洁的实现和近乎常数的操作时间复杂度成为解决连通性问题的利器。本文将深入解析5个经典竞赛题目从基础应用到高级技巧帮助C开发者掌握并查集的实战应用。1. 基础并查集Wireless_Network问题Wireless_Network是POJ上经典的并查集入门题题目描述了一系列计算机在特定距离内可以通信要求判断两台计算机是否能够直接或间接通信。#include vector #include cmath using namespace std; struct Point { double x, y; }; vectorint parent; vectorPoint 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号病人同组的病人数量展示了带权并查集在计数方面的应用。vectorint 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. 种类并查集关押罪犯问题关押罪犯问题需要将罪犯分成两组使同一组内的冲突值最小展示了种类并查集的典型应用。vectorint 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组in表示在B组敌人的敌人是朋友通过这种关系建立连接4. 食物链问题三态种类并查集食物链问题是种类并查集的经典扩展需要处理三种生物之间的捕食关系。vectorint 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吃b2: b吃a关系通过模3运算保持一致性5. 高级应用银河英雄传说银河英雄传说问题需要维护战舰之间的前后关系展示了带权并查集在距离计算中的应用。vectorint 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; }距离维护技巧dist数组记录每个节点到根节点的距离合并时更新距离和集合大小查询时通过距离差计算战舰间隔在实际竞赛中理解并查集的核心思想比记忆模板更重要。每个问题都有其特殊性需要根据具体场景调整并查集的实现方式。例如在处理动态连通性问题时可能需要结合离线处理在需要维护复杂关系时种类并查集往往能提供清晰的解决方案。