文章目录前言一、为什么需要并查集—— 解决痛点高效取舍二、并查集核心原理——极简逻辑一看就懂三、并查集核心优化——路径压缩按秩合并面试必写四、C面试版并查集完整版可直接手写五、面试高频考点解析重中之重六、C实战应用——面试真题解析直接套用模板七、学习建议与总结面试备考重点前言在C数据结构进阶学习中有一类结构看似简单却能高效解决“集合合并”与“元素归属查询”的核心问题——它就是并查集Union-Find。不同于二叉树的复杂遍历、哈希表的冲突处理并查集的核心逻辑极简却能在连通性问题、集合管理等场景中发挥巨大作用是面试中高频考察的“性价比之王”。本文专为C学习者、面试备考者打造全程贴合笔试面试场景从“为什么需要并查集”出发拆解核心原理、手写可直接复用的面试代码、讲解优化技巧再到实战真题解析帮你从“懂原理”到“能手写、会应用”彻底吃透并查集的所有高频考点。适合人群已掌握C基础vector、类与对象、了解基本数据结构想要进阶面试必备知识点或需要解决连通性、集合合并问题的学习者。一、为什么需要并查集—— 解决痛点高效取舍在日常开发和算法题中我们经常会遇到这类问题判断两个元素是否属于同一个集合如两个节点是否连通、两个学生是否在同一个班级将两个集合合并为一个集合如合并两个班级、连接两个网络节点统计集合的数量如岛屿数量、连通分量个数。如果用数组、链表或哈希表来实现这些操作要么查询效率低O(n)要么合并操作繁琐无法适配大规模数据如十万、百万级元素。而并查集的核心优势的就是查询、合并操作均接近O(1)时间复杂度且实现简单手写代码量极少是这类问题的最优解决方案。举个通俗例子假设我们有10个独立的人一开始每个人都是自己的“小团体”一个集合。当两个人成为朋友就将他们的团体合并想知道两个人是不是朋友只需查询他们是否属于同一个团体——这就是并查集的核心应用场景简单且高效。二、并查集核心原理——极简逻辑一看就懂并查集的核心思想是用树的结构表示集合每个集合对应一棵树树的根节点就是这个集合的“代表”标识。所有操作都围绕“找到代表”和“合并代表”展开核心只有两个操作Find查找和Union合并。1. 核心概念拆解集合的表示用一个数组parent存储每个元素的“父节点”parent[i]表示元素i的父节点是谁根节点当parent[i] i时说明i是这棵树的根节点集合的代表每个集合有且只有一个根节点Find查找找到元素x所在集合的根节点判断两个元素是否属于同一个集合根节点相同则属于同一集合Union合并找到两个元素x、y所在集合的根节点将其中一个根节点的父节点指向另一个根节点实现两个集合的合并。2. 未优化的基础实现理解核心先看最基础的并查集实现不考虑优化重点理解Find和Union的逻辑面试中不要直接写这个版本会有效率问题但能帮你吃透原理#include iostream #include vector using namespace std; // 基础版并查集未优化仅用于理解原理 class UnionFindBasic { private: vectorint parent; // 存储每个元素的父节点 public: // 初始化n个元素每个元素自成一个集合父节点指向自身 UnionFindBasic(int n) { parent.resize(n); for (int i 0; i n; i) { parent[i] i; // 根节点的父节点是自己 } } // Find操作查找x的根节点未优化路径长 int find(int x) { // 递归/循环找到根节点parent[x] x while (parent[x] ! x) { x parent[x]; // 向上追溯父节点 } return x; } // Union操作合并x和y所在的集合未优化可能导致树退化成链表 void unite(int x, int y) { int rootX find(x); // 找到x的根节点 int rootY find(y); // 找到y的根节点 if (rootX rootY) return; // 已属于同一个集合无需合并 // 直接将rootY的父节点指向rootX随意合并无优化 parent[rootY] rootX; } // 判断x和y是否属于同一个集合 bool isSameSet(int x, int y) { return find(x) find(y); } }; // 测试基础版 int main() { UnionFindBasic uf(5); // 5个元素0-4 uf.unite(0, 1); uf.unite(1, 2); uf.unite(3, 4); cout 0和2是否连通 (uf.isSameSet(0, 2) ? 是 : 否) endl; // 是 cout 0和3是否连通 (uf.isSameSet(0, 3) ? 是 : 否) endl; // 否 return 0; }3. 核心问题未优化的并查集为什么效率低基础版并查集存在一个致命问题合并时随意指向会导致树退化成链表。比如连续合并0-1、1-2、2-3、3-4树会变成一条单链4→3→2→1→0此时Find操作的时间复杂度会退化为O(n)失去高效优势。因此面试中必须掌握并查集的两个核心优化技巧——路径压缩和按秩合并这两个优化能让操作效率接近O(1)也是面试官重点考察的细节。三、并查集核心优化——路径压缩按秩合并面试必写两个优化技巧无需复杂逻辑只需在基础实现上稍作修改就能大幅提升效率也是面试手写并查集的“加分项”必须掌握。1. 优化一路径压缩Find操作优化核心思想在执行Find操作时将路径上的所有节点直接指向根节点减少后续Find操作的路径长度。相当于“扁平化”树的结构让后续查询更快。举个例子原本Find(4)需要经过4→3→2→0根节点路径压缩后4、3、2会直接指向0下次查询时直接就能找到根节点。实现方式递归/循环均可面试推荐递归代码更简洁// 路径压缩优化后的Find操作递归版面试首选 int find(int x) { // 如果x不是根节点递归找到根节点并将x的父节点直接指向根节点 if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩核心代码 } return parent[x]; }2. 优化二按秩合并Union操作优化核心思想合并两个集合时将“秩”树的高度较小的树合并到“秩”较大的树的根节点下避免树的高度过高进一步防止树退化成链表。补充“秩”可以理解为树的高度或深度初始时每个元素的秩为1自身为根节点高度为1当两个秩相等的树合并时合并后的根节点秩加1。实现方式新增一个rank数组存储每个根节点的秩合并时判断秩的大小选择最优合并方式。四、C面试版并查集完整版可直接手写结合路径压缩和按秩合并这是面试中最标准、最高效的并查集实现代码简洁、无冗余可直接用于笔试手写、算法题解题注释详细面试官一看就懂。#include iostream #include vector using namespace std; // C 并查集面试完整版含路径压缩按秩合并 class UnionFind { private: vectorint parent; // parent[i]元素i的父节点 vectorint rank; // rank[i]元素i为根节点时树的高度秩 public: // 初始化n个元素每个元素自成一个集合 UnionFind(int n) { parent.resize(n); rank.resize(n, 1); // 初始秩为1每个元素都是根节点 for (int i 0; i n; i) { parent[i] i; // 父节点指向自身 } } // Find操作查找x的根节点同时进行路径压缩递归版 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩直接指向根节点 } return parent[x]; } // Union操作合并x和y所在的集合按秩合并 void unite(int x, int y) { int rootX find(x); // 找到x的根节点 int rootY find(y); // 找到y的根节点 if (rootX rootY) return; // 已在同一集合直接返回 // 按秩合并秩小的树合并到秩大的树下 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; // rootX的父节点设为rootY } else { parent[rootY] rootX; // rootY的父节点设为rootX // 若秩相等合并后根节点的秩加1 if (rank[rootX] rank[rootY]) { rank[rootX]; } } } // 判断x和y是否属于同一个集合面试高频接口 bool isSameSet(int x, int y) { return find(x) find(y); } // 可选接口统计集合的数量面试偶尔考察 int getSetCount() { int count 0; for (int i 0; i parent.size(); i) { if (parent[i] i) { // 根节点的父节点是自身统计根节点数量 count; } } return count; } }; // 测试完整版并查集 int main() { UnionFind uf(5); // 5个元素0-4 uf.unite(0, 1); uf.unite(1, 2); uf.unite(3, 4); cout 0和2是否连通 (uf.isSameSet(0, 2) ? 是 : 否) endl; // 是 cout 0和3是否连通 (uf.isSameSet(0, 3) ? 是 : 否) endl; // 否 cout 当前集合数量 uf.getSetCount() endl; // 2{0,1,2}, {3,4} // 合并两个集合 uf.unite(2, 3); cout 合并后0和3是否连通 (uf.isSameSet(0, 3) ? 是 : 否) endl; // 是 cout 合并后集合数量 uf.getSetCount() endl; // 1 return 0; }五、面试高频考点解析重中之重并查集的面试考察集中在“原理理解”“代码手写”“场景应用”三个层面以下是高频考点必须逐一掌握避免踩坑。1. 核心考点必背考点1并查集的核心操作Find和Union的实现尤其是路径压缩和按秩合并的原理和代码面试必写少一个优化都会丢分考点2路径压缩和按秩合并的作用——避免树退化成链表将操作时间复杂度优化到接近O(1)考点3并查集的适用场景连通性问题、集合合并、统计集合数量考点4并查集的时间复杂度——Find和Union操作均为近乎O(1)严格来说是O(α(n))α是阿克曼函数增长极慢可视为常数。2. 面试避坑点丢分重灾区坑1忘记写路径压缩或按秩合并只写基础版并查集面试官会认为你没吃透并查集的优化逻辑坑2Union操作中直接合并元素x和y而不是合并它们的根节点会导致集合结构混乱查询结果错误坑3初始化时parent数组未赋值为自身根节点判断失效整个并查集无法正常工作坑4混淆“秩”的含义合并时搞反秩的大小应该将秩小的合并到秩大的树下反之会导致树变高。3. 手写代码注意事项面试细节代码简洁面试手写无需冗余注释关键步骤路径压缩、按秩合并保留即可边界处理初始化时注意n的范围避免数组越界可在构造函数中增加n0的判断可选体现代码健壮性接口完整至少实现find、unite、isSameSet三个核心接口getSetCount可作为补充提升印象分命名规范变量名清晰parent、rank避免晦涩命名如用f代替find。六、C实战应用——面试真题解析直接套用模板并查集的面试题大多是“模板题”只需套用上面的面试版代码稍作修改就能解决。以下是3道高频真题覆盖不同应用场景帮你巩固实战能力。真题1岛屿数量LeetCode 200题目描述给定一个由1陆地和0水组成的二维网格计算岛屿的数量。岛屿由相邻的陆地连接形成相邻指上下左右四个方向。解题思路将每个陆地1视为一个元素相邻的陆地合并到同一个集合最终集合的数量就是岛屿的数量。#include iostream #include vector using namespace std; class UnionFind { // 直接复用面试版并查集代码 private: vectorint parent; vectorint rank; public: UnionFind(int n) { parent.resize(n); rank.resize(n, 1); for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) parent[rootX] rootY; else { parent[rootY] rootX; if (rank[rootX] rank[rootY]) rank[rootX]; } } int getSetCount() { int count 0; for (int i 0; i parent.size(); i) { if (parent[i] i) count; } return count; } }; // 岛屿数量解题函数 int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(), n grid[0].size(); UnionFind uf(m * n); int waterCount 0; // 统计水的数量最终集合数 总集合数 - 水的数量 // 方向数组上下左右 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 0) { waterCount; continue; } // 遍历四个方向的相邻陆地合并 for (auto dir : dirs) { int x i dir[0]; int y j dir[1]; if (x 0 x m y 0 y n grid[x][y] 1) { // 将二维坐标转换为一维索引关键i*n j uf.unite(i * n j, x * n y); } } } } // 总元素数是m*n减去水的数量就是陆地的集合数岛屿数 return uf.getSetCount() - waterCount; } // 测试 int main() { vectorvectorchar grid { {1,1,0,0,0}, {1,1,0,0,0}, {0,0,1,0,0}, {0,0,0,1,1} }; cout 岛屿数量 numIslands(grid) endl; // 输出3 return 0; }真题2朋友圈LeetCode 547题目描述有n个学生每个学生都有自己的朋友圈朋友圈是相互的。给定一个n x n的矩阵isConnectedisConnected[i][j] 1表示第i和j个学生是朋友0表示不是。求朋友圈的数量。解题思路直接套用并查集学生为元素朋友关系为合并条件最终集合数量就是朋友圈数量。// 复用面试版并查集此处省略与真题1一致 int findCircleNum(vectorvectorint isConnected) { int n isConnected.size(); UnionFind uf(n); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (isConnected[i][j] 1) { uf.unite(i, j); } } } return uf.getSetCount(); }真题3冗余连接LeetCode 684题目描述在一棵无向树中添加一条边后会出现一个环找出这条导致环的冗余边。解题思路遍历每条边合并两个节点若合并前两个节点已属于同一个集合说明这条边是冗余边会形成环。// 复用面试版并查集此处省略 vectorint findRedundantConnection(vectorvectorint edges) { int n edges.size(); UnionFind uf(n 1); // 节点编号从1开始所以size为n1 for (auto edge : edges) { int x edge[0], y edge[1]; if (uf.isSameSet(x, y)) { return edge; // 已在同一集合这条边是冗余边 } uf.unite(x, y); } return {}; }七、学习建议与总结面试备考重点并查集是C数据结构进阶中最“好拿分”的知识点——逻辑简单、代码量少、应用场景固定只要掌握好以下几点就能轻松应对面试1. 先理解原理再手写代码不要死记硬背代码先搞懂“树表示集合”“Find找根”“Union合并根”的逻辑再动手写优化版代码每天默写1遍直到脱稿2. 重点掌握优化技巧路径压缩和按秩合并是面试核心必须能说清原理、写对代码这是区分“会用”和“吃透”的关键3. 多刷真题巩固LeetCode 200岛屿数量、547朋友圈、684冗余连接是必刷真题套用模板后重点练习“坐标转换”“边界处理”等细节4. 灵活适配场景记住并查集的核心应用——连通性、集合合并、集合统计遇到这类问题优先考虑并查集比DFS/BFS更高效、代码更简洁。最后总结并查集的核心不是“复杂的代码”而是“高效合并与查询”的设计思想。面试中只要能流畅手写优化版并查集代码结合真题场景灵活应用就能轻松拿下并查集相关的所有考点。小练习用并查集解决“省份数量”问题LeetCode 547的变种试试能不能直接套用模板写出代码欢迎在评论区交流你的思路