引言在前面图系列的最小生成树中我们第一次遇到了并查集——Kruskal 算法用并查集判断加入这条边会不会形成环。当时只用了几行代码带过今天来专门讲讲它。并查集Disjoint Set UnionDSU是一种管理元素分组的数据结构。它支持两种操作Find查找判断一个元素属于哪个集合Union合并把两个元素所在的集合合并成一个并查集代码极短核心不到 10 行但它是解决连通性判断、最小生成树、社交网络中的好友圈等问题的利器。第一部分并查集的基本概念一、数据结构并查集用森林来表示集合每个集合是一棵树树的根节点代表这个集合。存储方式一个parent数组parent[i]表示节点 i 的父节点。如果parent[i] i说明 i 是根节点。二、基本操作#define MAX_N 1000 int parent[MAX_N]; // 初始化每个元素自成一个集合 void init(int n) { for (int i 0; i n; i) { parent[i] i; // 自己是自己的父亲 → 自己是根 } } // 查找根节点最简版本 int find(int x) { while (parent[x] ! x) { x parent[x]; // 一直向上找到根 } return x; } // 合并两个集合 void unionSets(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 把一个根挂到另一个根下面 } }第二部分优化最简版本的查找是 O(h)h 为树高。如果树退化成链表查找就变成了 O(n)。并查集有两种经典优化路径压缩和按秩合并。一、路径压缩Path Compression查找时顺便把路径上所有节点都直接挂到根下面。查找一次后下次再查就是 O(1)。// 带路径压缩的查找递归写法 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } // 带路径压缩的查找迭代写法 int find_iter(int x) { int root x; while (parent[root] ! root) root parent[root]; // 找根 while (x ! root) { // 路径压缩 int next parent[x]; parent[x] root; x next; } return root; }二、按秩合并Union by Rank合并时把矮树挂到高树下面避免树变高。int rank[MAX_N]; // rank[i] 以 i 为根的树的高度上界 void init(int n) { for (int i 0; i n; i) { parent[i] i; rank[i] 0; // 初始高度为 0 } } void unionSets(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 if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; // 高度相等时挂完后高度 1 } }三、双优化后的复杂度同时使用路径压缩和按秩合并并查集的均摊时间复杂度为O(α(n))其中 α(n) 是反阿克曼函数——增长极其缓慢对于任何实际数据量α(n) ≤ 4。结论双优化后的并查集每次操作可以视为接近 O(1)。第三部分完整代码#include stdio.h #include stdlib.h #include stdbool.h #define MAX_N 1000 typedef struct { int parent[MAX_N]; int rank[MAX_N]; } UnionFind; // 初始化 void ufInit(UnionFind* uf, int n) { for (int i 0; i n; i) { uf-parent[i] i; uf-rank[i] 0; } } // 查找带路径压缩 int ufFind(UnionFind* uf, int x) { if (uf-parent[x] ! x) { uf-parent[x] ufFind(uf, uf-parent[x]); } return uf-parent[x]; } // 合并按秩合并 void ufUnion(UnionFind* uf, int x, int y) { int rootX ufFind(uf, x); int rootY ufFind(uf, y); if (rootX rootY) return; if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootX] rootY; } else if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootY] rootX; } else { uf-parent[rootY] rootX; uf-rank[rootX]; } } // 判断是否在同一集合 bool ufConnected(UnionFind* uf, int x, int y) { return ufFind(uf, x) ufFind(uf, y); }第四部分经典应用一、Kruskal 最小生成树// 判断加入边 (u,v) 是否成环 if (!ufConnected(uf, u, v)) { ufUnion(uf, u, v); // 加入这条边 }二、朋友圈问题// LeetCode 547省份数量 int findCircleNum(int** isConnected, int n) { UnionFind uf; ufInit(uf, n); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (isConnected[i][j]) { ufUnion(uf, i, j); } } } // 统计不同根的数量 朋友圈数量 int count 0; for (int i 0; i n; i) { if (ufFind(uf, i) i) count; } return count; }三、判断无向图是否有环bool hasCycle(int n, int edges[][2], int edgeCount) { UnionFind uf; ufInit(uf, n); for (int i 0; i edgeCount; i) { int u edges[i][0]; int v edges[i][1]; if (ufConnected(uf, u, v)) { return true; // 已经在同一集合 → 加这条边会成环 } ufUnion(uf, u, v); } return false; }四、连通分量数量int countComponents(int n, int edges[][2], int edgeCount) { UnionFind uf; ufInit(uf, n); for (int i 0; i edgeCount; i) { ufUnion(uf, edges[i][0], edges[i][1]); } int count 0; for (int i 0; i n; i) { if (ufFind(uf, i) i) count; } return count; }第五部分面试题1. Q并查集的时间复杂度A只用路径压缩或只用按秩合并是 O(log n)。两者同时使用均摊时间复杂度是 O(α(n))α(n) 是反阿克曼函数对任何实际数据量 ≤ 4可视为接近 O(1)。2. Q路径压缩的原理A在 find 时把查找路径上经过的所有节点直接挂到根下面。下次再查这些节点就是 O(1)。如果只写路径压缩不写按秩合并最坏情况仍然是 O(log n)。3. Q为什么按秩合并比按大小合并好A效果相同都是让树更平衡。按秩合并用 rank 表示高度上界实现略微简单。按大小合并size同样有效选哪个都可以但不能两个都不写。总结一、核心要点要点内容存储parent[i]表示 i 的父节点parent[i]i表示是根查找find(x)一直向上找到根合并union(x,y)把两个根连在一起路径压缩find 时把路径上所有节点直接挂到根按秩合并把矮树挂到高树下避免树变高复杂度双优化后接近 O(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 union(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (rank[rx] rank[ry]) parent[rx] ry; else if (rank[rx] rank[ry]) parent[ry] rx; else { parent[ry] rx; rank[rx]; } }三、一句话记忆并查集用parent数组存父节点find找根并路径压缩union按秩合并把矮树挂高树。双优化后均摊复杂度接近 O(1)用于快速判断元素是否在同一集合是 Kruskal 和连通性问题的核心数据结构。
并查集：10行代码搞定连通性问题
引言在前面图系列的最小生成树中我们第一次遇到了并查集——Kruskal 算法用并查集判断加入这条边会不会形成环。当时只用了几行代码带过今天来专门讲讲它。并查集Disjoint Set UnionDSU是一种管理元素分组的数据结构。它支持两种操作Find查找判断一个元素属于哪个集合Union合并把两个元素所在的集合合并成一个并查集代码极短核心不到 10 行但它是解决连通性判断、最小生成树、社交网络中的好友圈等问题的利器。第一部分并查集的基本概念一、数据结构并查集用森林来表示集合每个集合是一棵树树的根节点代表这个集合。存储方式一个parent数组parent[i]表示节点 i 的父节点。如果parent[i] i说明 i 是根节点。二、基本操作#define MAX_N 1000 int parent[MAX_N]; // 初始化每个元素自成一个集合 void init(int n) { for (int i 0; i n; i) { parent[i] i; // 自己是自己的父亲 → 自己是根 } } // 查找根节点最简版本 int find(int x) { while (parent[x] ! x) { x parent[x]; // 一直向上找到根 } return x; } // 合并两个集合 void unionSets(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 把一个根挂到另一个根下面 } }第二部分优化最简版本的查找是 O(h)h 为树高。如果树退化成链表查找就变成了 O(n)。并查集有两种经典优化路径压缩和按秩合并。一、路径压缩Path Compression查找时顺便把路径上所有节点都直接挂到根下面。查找一次后下次再查就是 O(1)。// 带路径压缩的查找递归写法 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } // 带路径压缩的查找迭代写法 int find_iter(int x) { int root x; while (parent[root] ! root) root parent[root]; // 找根 while (x ! root) { // 路径压缩 int next parent[x]; parent[x] root; x next; } return root; }二、按秩合并Union by Rank合并时把矮树挂到高树下面避免树变高。int rank[MAX_N]; // rank[i] 以 i 为根的树的高度上界 void init(int n) { for (int i 0; i n; i) { parent[i] i; rank[i] 0; // 初始高度为 0 } } void unionSets(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 if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; // 高度相等时挂完后高度 1 } }三、双优化后的复杂度同时使用路径压缩和按秩合并并查集的均摊时间复杂度为O(α(n))其中 α(n) 是反阿克曼函数——增长极其缓慢对于任何实际数据量α(n) ≤ 4。结论双优化后的并查集每次操作可以视为接近 O(1)。第三部分完整代码#include stdio.h #include stdlib.h #include stdbool.h #define MAX_N 1000 typedef struct { int parent[MAX_N]; int rank[MAX_N]; } UnionFind; // 初始化 void ufInit(UnionFind* uf, int n) { for (int i 0; i n; i) { uf-parent[i] i; uf-rank[i] 0; } } // 查找带路径压缩 int ufFind(UnionFind* uf, int x) { if (uf-parent[x] ! x) { uf-parent[x] ufFind(uf, uf-parent[x]); } return uf-parent[x]; } // 合并按秩合并 void ufUnion(UnionFind* uf, int x, int y) { int rootX ufFind(uf, x); int rootY ufFind(uf, y); if (rootX rootY) return; if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootX] rootY; } else if (uf-rank[rootX] uf-rank[rootY]) { uf-parent[rootY] rootX; } else { uf-parent[rootY] rootX; uf-rank[rootX]; } } // 判断是否在同一集合 bool ufConnected(UnionFind* uf, int x, int y) { return ufFind(uf, x) ufFind(uf, y); }第四部分经典应用一、Kruskal 最小生成树// 判断加入边 (u,v) 是否成环 if (!ufConnected(uf, u, v)) { ufUnion(uf, u, v); // 加入这条边 }二、朋友圈问题// LeetCode 547省份数量 int findCircleNum(int** isConnected, int n) { UnionFind uf; ufInit(uf, n); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (isConnected[i][j]) { ufUnion(uf, i, j); } } } // 统计不同根的数量 朋友圈数量 int count 0; for (int i 0; i n; i) { if (ufFind(uf, i) i) count; } return count; }三、判断无向图是否有环bool hasCycle(int n, int edges[][2], int edgeCount) { UnionFind uf; ufInit(uf, n); for (int i 0; i edgeCount; i) { int u edges[i][0]; int v edges[i][1]; if (ufConnected(uf, u, v)) { return true; // 已经在同一集合 → 加这条边会成环 } ufUnion(uf, u, v); } return false; }四、连通分量数量int countComponents(int n, int edges[][2], int edgeCount) { UnionFind uf; ufInit(uf, n); for (int i 0; i edgeCount; i) { ufUnion(uf, edges[i][0], edges[i][1]); } int count 0; for (int i 0; i n; i) { if (ufFind(uf, i) i) count; } return count; }第五部分面试题1. Q并查集的时间复杂度A只用路径压缩或只用按秩合并是 O(log n)。两者同时使用均摊时间复杂度是 O(α(n))α(n) 是反阿克曼函数对任何实际数据量 ≤ 4可视为接近 O(1)。2. Q路径压缩的原理A在 find 时把查找路径上经过的所有节点直接挂到根下面。下次再查这些节点就是 O(1)。如果只写路径压缩不写按秩合并最坏情况仍然是 O(log n)。3. Q为什么按秩合并比按大小合并好A效果相同都是让树更平衡。按秩合并用 rank 表示高度上界实现略微简单。按大小合并size同样有效选哪个都可以但不能两个都不写。总结一、核心要点要点内容存储parent[i]表示 i 的父节点parent[i]i表示是根查找find(x)一直向上找到根合并union(x,y)把两个根连在一起路径压缩find 时把路径上所有节点直接挂到根按秩合并把矮树挂到高树下避免树变高复杂度双优化后接近 O(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 union(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (rank[rx] rank[ry]) parent[rx] ry; else if (rank[rx] rank[ry]) parent[ry] rx; else { parent[ry] rx; rank[rx]; } }三、一句话记忆并查集用parent数组存父节点find找根并路径压缩union按秩合并把矮树挂高树。双优化后均摊复杂度接近 O(1)用于快速判断元素是否在同一集合是 Kruskal 和连通性问题的核心数据结构。
