Count Connected Components in an Undirected Graph
Count Connected Components in an Undirected Graph
开始编码给定 n 个节点(编号 0 到 n-1)和无向 edges 列表。两个节点属于同一 连通分量,当且仅当它们之间存在边构成的路径;没有任何边的孤立节点自身构成单点分量。返回图中连通分量的数量。
实现 solution(n, edges) -> int。先建邻接表,然后从每个未访问节点出发跑 BFS 或 DFS,每跑完一轮把计数器自增一次 —— 总成本 O(N + E)。并查集是等价的替代方案。允许输入自环与重复边,且不影响分量计数。
例如,solution(5, [[0, 1], [1, 2], [3, 4]]) 返回 2 —— 节点 {0, 1, 2} 通过节点 1 连成一条链,构成一个分量;{3, 4} 构成另一个分量。solution(5, [[0, 1], [1, 2], [2, 3], [3, 4]]) 返回 1 —— 一条 4 边长链把全部 5 个节点连通。solution(4, []) 返回 4 —— 无边时每个节点都是孤立分量。
实战背景
连通分量是 trade-graph 分析中簇级 factor 构造 的核心原语。每当两只 ticker 出现在同一 broker basket(或同一 session 窗口的对冲交易)时连一条边,跑连通分量,得到的 cluster ID 即可作为类别 factor —— 同一 cluster 中的名字往往共享某种未观测的需求压力,横截面模型可以把 cluster 作为控制变量或图先验。同样的原语出现在监管侦测(basket detection —— 一个覆盖整个板块成员的巨大分量提示板块整体平仓)、对手方风险(双边敞口链)、以及执行分析(哪些场所路由到哪些流动性池)中。实际操盘时:静态窗口批量处理,BFS/DFS 是更称手的工具;边流式到达、希望增量更新簇结构而无需重建邻接表时,并查集更合适。两者都该在工具箱里。
约束条件
- 0 ≤ `n` ≤ 10000 —— 节点数,编号为 `0` 到 `n-1`
- 0 ≤ `len(edges)` ≤ 100000 —— 每条边为 `[u, v]`,且 `0 ≤ u, v < n`
- 图为无向图 —— 边 `[u, v]` 同时连接 `u` 与 `v` 双向
- 允许自环 (`u == v`) 和重复边 —— 不影响连通分量数
- 边界情况:`n == 0` 返回 `0`(无节点、无分量)
样例
Case 1 · statement-example: n=0 returns 0
输入: [0,[]]
期望: 0
n=0 时图中没有节点,连通分量数为 0。
Case 2 · statement-example: single node with no edges is one component
输入: [1,[]]
期望: 1
单个节点没有任何边时自身就是一个孤立分量,返回 1。
Case 3 · statement-example: 5 nodes, no edges → 5 singletons
输入: [5,[]]
期望: 5
5 个节点没有任何边,每个节点都是孤立分量,共 5 个。
Case 4 · statement-example: two components plus one chain
输入: [5,[[0,1],[1,2],[3,4]]]
期望: 2
0-1-2 通过节点 1 串成一个分量,3-4 是另一个分量,共 2 个。
Case 5 · statement-example: long chain fully connects all nodes
输入: [5,[[0,1],[1,2],[2,3],[3,4]]]
期望: 1
4 条边形成一条从 0 到 4 的链,所有 5 个节点连通,只有 1 个分量。
Case 6 · star topology — every spoke connects through hub
输入: [5,[[0,1],[0,2],[0,3],[0,4]]]
期望: 1
星型结构:节点 0 是中心,4 条辐条把所有节点连成一个分量。
Case 7 · duplicate edges are idempotent
输入: [5,[[0,1],[0,1],[1,0]]]
期望: 4
三次重复的 0-1 边只联通了 0 和 1;节点 2、3、4 仍是孤点,共 4 个分量。
Case 8 · self-loop does not change component count
输入: [3,[[0,0],[1,2]]]
期望: 2
自环 [0, 0] 不改变连通性。1-2 合并为一个分量,0 仍是孤点,共 2 个分量。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: n=0 returns 0
输入: [0,[]]
期望: 0
n=0 时图中没有节点,连通分量数为 0。
Case 2 · statement-example: single node with no edges is one component
输入: [1,[]]
期望: 1
单个节点没有任何边时自身就是一个孤立分量,返回 1。
Case 3 · statement-example: 5 nodes, no edges → 5 singletons
输入: [5,[]]
期望: 5
5 个节点没有任何边,每个节点都是孤立分量,共 5 个。
Case 4 · statement-example: two components plus one chain
输入: [5,[[0,1],[1,2],[3,4]]]
期望: 2
0-1-2 通过节点 1 串成一个分量,3-4 是另一个分量,共 2 个。
Case 5 · statement-example: long chain fully connects all nodes
输入: [5,[[0,1],[1,2],[2,3],[3,4]]]
期望: 1
4 条边形成一条从 0 到 4 的链,所有 5 个节点连通,只有 1 个分量。
Case 6 · star topology — every spoke connects through hub
输入: [5,[[0,1],[0,2],[0,3],[0,4]]]
期望: 1
星型结构:节点 0 是中心,4 条辐条把所有节点连成一个分量。
Case 7 · duplicate edges are idempotent
输入: [5,[[0,1],[0,1],[1,0]]]
期望: 4
三次重复的 0-1 边只联通了 0 和 1;节点 2、3、4 仍是孤点,共 4 个分量。
Case 8 · self-loop does not change component count
输入: [3,[[0,0],[1,2]]]
期望: 2
自环 [0, 0] 不改变连通性。1-2 合并为一个分量,0 仍是孤点,共 2 个分量。