企业官网建设流程全解析

LeetCode 547. Number of Provinces：Go 语言并查集与 DFS FloodFill 双解法详解

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode-Go 仓库中 0547. Number of Provinces 题解文档为核心，完整讲解「省份数量」（朋友圈）问题的题目模型、两种官方推荐的解题思路，并深入仓库源码印证并查集（Union-Find）与 DFS FloodFill 两种解法的真实实现与测试验证。读完本文，你将掌握「连通分量计数」这一类图论问题的标准套路，并能在 Go 中独立复现两套可运行的解法。

题目：朋友圈 / 省份数量的连通分量模型

547. Number of Provinces（原题名 Friend Circles）是一道经典的图论入门题，核心在于识别并统计**连通分量（connected component）**的数量。

题目描述如下：班上有N名学生，其中有些人是朋友，有些不是。友谊关系具有传递性——如果 A 是 B 的直接朋友，B 是 C 的直接朋友，那么 A 与 C 就是间接朋友；一个「朋友圈」（friend circle）就是由直接或间接朋友组成的群体。

给定一个N×N的矩阵M表示学生之间的朋友关系：

• 若M[i][j] = 1，表示第 i 和第 j 名学生互为直接朋友；
• 否则视为不认识；
• 要求输出所有学生中朋友圈（即连通分量）的总数。

从图论视角看，把每名学生看作顶点，M[i][j] = 1看作一条无向边，那么本题就是在无向图上统计连通分量个数。这也是后续许多图论题（岛屿数量、冗余连接、省份划分等）的公共基础。

示例分析

示例 1：

Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2

第 0 名与第 1 名学生互为直接朋友，处于同一个朋友圈；第 2 名学生独自构成一个朋友圈。因此答案是 2。

示例 2：

Input: [[1,1,0], [1,1,1], [0,1,1]] Output: 1

第 0 名与第 1 名直接朋友，第 1 名与第 2 名直接朋友，由传递性可知第 0 名与第 2 名是间接朋友。三人都在同一个朋友圈，因此答案是 1。

题目约束

• N的取值范围是[1, 200]；
• 对所有学生恒有M[i][i] = 1（自己与自己必然是朋友）；
• 若M[i][j] = 1，则必有M[j][i] = 1（矩阵沿主对角线对称）。

后两条约束意味着矩阵是对称矩阵，扫描时只需遍历下三角（或上三角）即可避免重复处理，这正是仓库解法一中内层循环j <= i的依据。

解题思路总览：连通分量计数的两种标准做法

原文档明确指出这题有 2 种解法：

1. 并查集（Union-Find）：依次扫描矩阵，如果两个人认识且当前所属集合的根不同，就执行 union 合并。扫完整个矩阵后，统计还有几个不同的根（集合），即为最终答案。
2. DFS 或 BFS（FloodFill 染色法）：利用 FloodFill 的思路逐次「染色」，每染完一个连通分量计数器加一；扫完整个矩阵后，计数器即为最终结果。

下面分别结合 LeetCode-Go 仓库的真实源码逐行剖析这两种实现。

解法一：基于模板并查集的实现

仓库解法一位于 547. Number of Provinces.go，完整代码如下：

// 解法一 并查集 func findCircleNum(M [][]int) int { n := len(M) if n == 0 { return 0 } uf := template.UnionFind{} uf.Init(n) for i := 0; i < n; i++ { for j := 0; j <= i; j++ { if M[i][j] == 1 { uf.Union(i, j) } } } return uf.TotalCount() }

算法流程分四步：

1. 边界处理：当n == 0时直接返回 0；
2. 初始化：uf.Init(n)创建 n 个独立集合，每个学生初始时自成一个朋友圈；
3. 遍历合并：双层循环只扫描下三角区域（j <= i，主对角线包含在内），遇到M[i][j] == 1就执行uf.Union(i, j)。由于矩阵对称且对角线恒为 1，这种扫描方式既覆盖了全部朋友关系，又不会重复合并；
4. 返回结果：uf.TotalCount()返回当前剩余集合的数量，即为朋友圈总数。

值得注意的是，findCircleNum复用了仓库 template/UnionFind.go 中的template.UnionFind模板，而不是在题解文件内重新实现。这种「题目专用逻辑写在题解里、通用数据结构沉淀在模板包」的组织方式，是 LeetCode-Go 仓库一贯的风格。

深入模板实现：路径压缩 + 秩优化

template.UnionFind定义在 template/UnionFind.go，注释明确标注其使用了路径压缩 + 秩优化两项经典优化：

// UnionFind defind // 路径压缩 + 秩优化 type UnionFind struct { parent, rank []int count int }

各成员含义如下：

Init：建立 n 个独立集合

func (uf *UnionFind) Init(n int) { uf.count = n uf.parent = make([]int, n) uf.rank = make([]int, n) for i := range uf.parent { uf.parent[i] = i } }

初始时每个学生的父节点都是自己，count = n，表示 n 个各自独立的朋友圈。

Find：查找根节点并做路径压缩

func (uf *UnionFind) Find(p int) int { root := p for root != uf.parent[root] { root = uf.parent[root] } // compress path for p != uf.parent[p] { tmp := uf.parent[p] uf.parent[p] = root p = tmp } return root }

先沿父指针一路向上找到根root，再走第二遍循环把路径上每个节点直接挂到根上（路径压缩）。这保证了后续查找接近 O(1) 均摊复杂度。

Union：按秩合并

func (uf *UnionFind) Union(p, q int) { proot := uf.Find(p) qroot := uf.Find(q) if proot == qroot { return } if uf.rank[qroot] > uf.rank[proot] { uf.parent[proot] = qroot } else { uf.parent[qroot] = proot if uf.rank[proot] == uf.rank[qroot] { uf.rank[proot]++ } } uf.count-- }

合并逻辑的关键点：

• 若两个节点已在同一集合（proot == qroot），直接返回，count不变；
• 否则按秩合并：秩大的树作为根，秩相等时任意指定一方为根并让该根秩加一，防止树退化成链表；
• 只有真正发生合并时才count--。

TotalCount：返回连通分量数

func (uf *UnionFind) TotalCount() int { return uf.count }

count从 n 开始、每次成功合并减一，所以最终值恰好就是朋友圈总数。

时间复杂度分析

• 每次Union调用包含两次带路径压缩的Find，均摊复杂度近似 O(α(n))（α 为反阿克曼函数，可视为常数）；
• 矩阵共 n² 个元素，下三角扫描约 n(n+1)/2 次判断；
• 总时间复杂度约为 O(n²·α(n))，空间复杂度 O(n)。

解法二：DFS FloodFill 染色实现

仓库解法二位于 547. Number of Provinces.go，利用深度优先搜索对每个未访问的学生执行 FloodFill：

// 解法二 FloodFill DFS 暴力解法 func findCircleNum1(M [][]int) int { if len(M) == 0 { return 0 } visited := make([]bool, len(M)) res := 0 for i := range M { if !visited[i] { dfs547(M, i, visited) res++ } } return res } func dfs547(M [][]int, cur int, visited []bool) { visited[cur] = true for j := 0; j < len(M[cur]); j++ { if !visited[j] && M[cur][j] == 1 { dfs547(M, j, visited) } } }

执行过程：

1. 维护长度为 n 的visited布尔数组，记录哪些学生已被染入某个朋友圈；
2. 遍历每一名学生，若尚未访问，说明发现了一个新的连通分量，调用dfs547将其整个朋友圈染完，同时res++；
3. dfs547从当前学生cur出发，标记visited[cur] = true，再递归遍历所有M[cur][j] == 1且未访问的学生，把整条朋友链全部染色；
4. 主循环结束后res即为朋友圈总数。

之所以把 DFS 辅助函数命名为dfs547，是仓库为避免不同题解中同包内辅助函数命名冲突而采用的编号后缀约定，与本仓库中其他题目的dfsXXX命名风格一致。

从语义上讲，解法二与解法一完全等价：DFS 每完成一次递归展开，就等价于并查集中的一次集合合并；res与TotalCount()最终都收敛到同一个连通分量数。也可以将dfs547的递归展开改写成显式栈或队列（BFS），得到第三种实现，思想完全一致。

时间复杂度分析

每个节点最多被visited标记一次，每行扫描长度为 n，因此时间复杂度为 O(n²)，空间复杂度 O(n)（visited 数组 + 递归栈深度）。

测试验证：四种用例覆盖关键边界

仓库为本题提供了完整的单元测试 547. Number of Provinces_test.go，采用仓库统一的「para/ans 结构体 + 表驱动」测试风格，覆盖了 4 个关键场景：

值得注意的是，第一个用例中矩阵对角线以外的元素全部为 0，但M[i][i] = 1恒成立，输出为 3，恰好验证了「对角线上的自朋友关系不会被错误地合并为同一个朋友圈」。

测试函数Test_Problem547对每组用例同时断言两个解法（findCircleNum与findCircleNum1），任一解法输出不符即通过t.Fatalf失败，从而保证并查集与 DFS 两种实现互相印证、行为一致：

ret := findCircleNum(p.one) ... if ret != a.one { t.Fatalf("findCircleNum(%v) = %v, want %v", p.one, ret, a.one) } if ret1 := findCircleNum1(p.one); ret1 != a.one { t.Fatalf("findCircleNum1(%v) = %v, want %v", p.one, ret1, a.one) }

如何运行测试

在仓库根目录执行以下命令即可运行本题测试（仓库 go.mod 声明 Go 1.19，并已通过replace指令将template包本地化关联到 template/UnionFind.go 所在的源码目录）：

go test -v -run Test_Problem547 ./leetcode/0547.Number-of-Provinces/

若需生成并查看全仓库覆盖率报告，可参照 gotest.sh 中的做法：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

该脚本注释还说明了一个细节：旧写法对每个包分别-coverprofile再cat追加会产出带多个mode: atomic头部的非法 coverage 文件，Go 1.10+ 支持一次性对多包生成单个合法 profile，这正是本仓库gotest.sh采用单命令写法的原因。

总结：一种模型，两套模板

回顾本题，可以提炼出连通分量计数的通用套路：

1. 建模：把实体抽象为顶点、把二元关系抽象为无向边，问题转化为统计无向图连通分量个数；
2. 选择工具：需要动态合并或查询集合归属时用并查集（template/UnionFind.go 已封装好路径压缩 + 按秩合并）；只需要统计数量时用DFS/BFS FloodFill更直观；
3. 验证：善用表驱动测试，把题目示例、边界空输入、对角线自环等场景全部纳入断言，两个解法互相对拍，确保正确性。

本题的两种解法在 LeetCode-Go 仓库中均保持 100% 测试覆盖（测试文件对每组用例双解法断言），代码风格遵循 Google Go 代码规范。你可以直接在 leetcode/0547.Number-of-Provinces 目录中查看完整题解，也可以进一步阅读 template/UnionFind.go 中另一个UnionFindCount模板（支持统计每个集合元素个数与最大集合大小），它对于「带规模统计的连通分量」类问题同样开箱即用。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go