尧图网站建设 
LeetCode 547. Number of ProvincesGo 语言并查集与 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看作一条无向边那么本题就是在无向图上统计连通分量个数。这也是后续许多图论题岛屿数量、冗余连接、省份划分等的公共基础。示例分析示例 1Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2第 0 名与第 1 名学生互为直接朋友处于同一个朋友圈第 2 名学生独自构成一个朋友圈。因此答案是 2。示例 2Input: [[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 种解法并查集Union-Find依次扫描矩阵如果两个人认识且当前所属集合的根不同就执行 union 合并。扫完整个矩阵后统计还有几个不同的根集合即为最终答案。DFS 或 BFSFloodFill 染色法利用 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() }算法流程分四步边界处理当n 0时直接返回 0初始化uf.Init(n)创建 n 个独立集合每个学生初始时自成一个朋友圈遍历合并双层循环只扫描下三角区域j i主对角线包含在内遇到M[i][j] 1就执行uf.Union(i, j)。由于矩阵对称且对角线恒为 1这种扫描方式既覆盖了全部朋友关系又不会重复合并返回结果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 }各成员含义如下成员作用parent记录每个节点的父节点父节点指向自身即代表该节点是集合根rank记录树的秩近似高度用于合并时把矮树挂到高树下count当前集合总数每次成功合并减一最终即为连通分量个数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(n1)/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) } } }执行过程维护长度为 n 的visited布尔数组记录哪些学生已被染入某个朋友圈遍历每一名学生若尚未访问说明发现了一个新的连通分量调用dfs547将其整个朋友圈染完同时resdfs547从当前学生cur出发标记visited[cur] true再递归遍历所有M[cur][j] 1且未访问的学生把整条朋友链全部染色主循环结束后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,0,0],[0,1,0],[0,0,0]]3三人互不相识对角线除外各自成圈[[1,1,0],[1,1,0],[0,0,1]]2对应题目示例 1[[1,1,0],[1,1,1],[0,1,1]]2 → 1对应题目示例 2覆盖间接朋友传递[][]0空矩阵边界值得注意的是第一个用例中矩阵对角线以外的元素全部为 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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本注释还说明了一个细节旧写法对每个包分别-coverprofile再cat追加会产出带多个mode: atomic头部的非法 coverage 文件Go 1.10 支持一次性对多包生成单个合法 profile这正是本仓库gotest.sh采用单命令写法的原因。总结一种模型两套模板回顾本题可以提炼出连通分量计数的通用套路建模把实体抽象为顶点、把二元关系抽象为无向边问题转化为统计无向图连通分量个数选择工具需要动态合并或查询集合归属时用并查集template/UnionFind.go 已封装好路径压缩 按秩合并只需要统计数量时用DFS/BFS FloodFill更直观验证善用表驱动测试把题目示例、边界空输入、对角线自环等场景全部纳入断言两个解法互相对拍确保正确性。本题的两种解法在 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 547. Number of Provinces：Go 语言并查集与 DFS FloodFill 双解法详解
LeetCode 547. Number of ProvincesGo 语言并查集与 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看作一条无向边那么本题就是在无向图上统计连通分量个数。这也是后续许多图论题岛屿数量、冗余连接、省份划分等的公共基础。示例分析示例 1Input: [[1,1,0], [1,1,0], [0,0,1]] Output: 2第 0 名与第 1 名学生互为直接朋友处于同一个朋友圈第 2 名学生独自构成一个朋友圈。因此答案是 2。示例 2Input: [[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 种解法并查集Union-Find依次扫描矩阵如果两个人认识且当前所属集合的根不同就执行 union 合并。扫完整个矩阵后统计还有几个不同的根集合即为最终答案。DFS 或 BFSFloodFill 染色法利用 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() }算法流程分四步边界处理当n 0时直接返回 0初始化uf.Init(n)创建 n 个独立集合每个学生初始时自成一个朋友圈遍历合并双层循环只扫描下三角区域j i主对角线包含在内遇到M[i][j] 1就执行uf.Union(i, j)。由于矩阵对称且对角线恒为 1这种扫描方式既覆盖了全部朋友关系又不会重复合并返回结果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 }各成员含义如下成员作用parent记录每个节点的父节点父节点指向自身即代表该节点是集合根rank记录树的秩近似高度用于合并时把矮树挂到高树下count当前集合总数每次成功合并减一最终即为连通分量个数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(n1)/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) } } }执行过程维护长度为 n 的visited布尔数组记录哪些学生已被染入某个朋友圈遍历每一名学生若尚未访问说明发现了一个新的连通分量调用dfs547将其整个朋友圈染完同时resdfs547从当前学生cur出发标记visited[cur] true再递归遍历所有M[cur][j] 1且未访问的学生把整条朋友链全部染色主循环结束后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,0,0],[0,1,0],[0,0,0]]3三人互不相识对角线除外各自成圈[[1,1,0],[1,1,0],[0,0,1]]2对应题目示例 1[[1,1,0],[1,1,1],[0,1,1]]2 → 1对应题目示例 2覆盖间接朋友传递[][]0空矩阵边界值得注意的是第一个用例中矩阵对角线以外的元素全部为 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 -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本注释还说明了一个细节旧写法对每个包分别-coverprofile再cat追加会产出带多个mode: atomic头部的非法 coverage 文件Go 1.10 支持一次性对多包生成单个合法 profile这正是本仓库gotest.sh采用单命令写法的原因。总结一种模型两套模板回顾本题可以提炼出连通分量计数的通用套路建模把实体抽象为顶点、把二元关系抽象为无向边问题转化为统计无向图连通分量个数选择工具需要动态合并或查询集合归属时用并查集template/UnionFind.go 已封装好路径压缩 按秩合并只需要统计数量时用DFS/BFS FloodFill更直观验证善用表驱动测试把题目示例、边界空输入、对角线自环等场景全部纳入断言两个解法互相对拍确保正确性。本题的两种解法在 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考