并查集

题目要求 给你一个 m x n 的二维字符网格 grid： "1" 表示陆地 "0" 表示水 题目要求返回岛屿数量。 一个岛屿由水平或垂直相邻的陆地组成。对角线相邻不算连通。可以认为网格四周都被水包围。 输入输出 输入：grid: List[List[str]] 输出：岛屿数量 int 只看上下左右四个方向。 "0" 水格子不能算作岛屿的一部分。 示例 输入： [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 这些陆地通过上下左右连成一整块，所以答案是 1。 输入： [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 这里有三块互不连通的陆地，所以答案是 3。 约束 m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 只会是 "0" 或 "1" 这一题可以用 DFS 或 BFS 做。这里的目标是练并查集：把每块陆地当成一个节点，把相邻陆地合并，最后留下的陆地连通分量数量就是岛屿数量。 ...

题目要求 题目给你一个无向图。这个图原本是一棵有 n 个节点的树，节点编号是 1..n，后来额外加了一条边。 树的定义是： 连通 没有环 加上一条额外边之后，图仍然连通，但会出现一个环。 现在给定边数组 edges，其中 edges[i] = [a, b] 表示节点 a 和节点 b 之间有一条无向边。题目要求返回一条可以删除的边，使剩下的图重新变成树。 如果有多个答案，返回在输入中最后出现的那条。 输入输出 输入：edges: List[List[int]] 输出：一条边 List[int] n == len(edges) 节点编号是 1..n 图中没有重复边 给定图是连通的 示例 输入：edges = [[1,2],[1,3],[2,3]] 输出：[2,3] 前两条边形成一棵树： 1 - 2 | 3 再加入 [2,3]，2 和 3 之间已经能通过 2 -> 1 -> 3 连通。现在再加直接边，就形成环。 输入：edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] 输出：[1,4] 加入 [1,4] 之前，1 和 4 已经能通过 1 -> 2 -> 3 -> 4 连通，所以 [1,4] 是冗余边。 ...

副标题 / 摘要 并查集不是从 find 和 union 这两个函数名开始背。它要解决的问题是：怎样判断两个点是否已经属于同一个集合，并在看到一条连接关系时把两个集合合并。 预计阅读时长：10~12 分钟 标签：Hot100、并查集、Union-Find、DSU、图 SEO 关键词：并查集, Union-Find, DSU, find, union, count, 路径压缩 元描述：用 Python 从零推导并查集模板，讲清 parent、find、union、count、路径压缩和连通分量计数。 A — Algorithm（从集合合并压力开始） 小任务：不断合并集合，并回答连通性 假设有 5 个点： 0, 1, 2, 3, 4 一开始，每个点都是一个独立集合： {0}, {1}, {2}, {3}, {4} 现在依次发生两次合并： union(0, 1) union(1, 2) 我们想回答三个问题： 0 和 2 是否在同一个集合？ 3 和 4 是否在同一个集合？ 当前一共有几个集合？ 手工看答案是： {0, 1, 2}, {3}, {4} 所以： 0 和 2 在同一个集合 3 和 4 不在同一个集合 当前 count = 3 这就是并查集要解决的核心任务： ...

题目要求 给你一个 n x n 的矩阵 isConnected，其中有 n 个城市。 如果 isConnected[i][j] == 1，说明城市 i 和城市 j 直接相连；如果两个城市可以通过若干个直接相连的城市互相到达，它们就属于同一个省份。 题目要求返回省份的总数。 这里最容易误解的一点是：题目不是让我们数矩阵里有多少个 1，也不是只看直接相连的城市对。它真正要数的是： 直接或间接连接在一起的城市组有多少个。 换成图的语言，就是： 给定一个无向图的邻接矩阵，返回这个图的连通分量数量。 输入输出 输入：isConnected: List[List[int]] 输出：省份数量 int 城市编号可以按 0..n-1 理解。 isConnected[i][j] == 1 表示城市 i 和城市 j 之间有边。 isConnected[i][j] == 0 表示城市 i 和城市 j 没有直接边。 示例 1 输入：isConnected = [ [1, 1, 0], [1, 1, 0], [0, 0, 1] ] 输出：2 城市 0 和城市 1 直接相连，所以它们属于同一个省份。 ...