返回题库|

图连通性

中等阿里巴巴

图连通性

中等阿里巴巴并查集

题目描述

给定一个由n个节点组成的图,节点编号从0到n-1。你需要实现一个数据结构来动态地添加边并查询两个节点是否连通。实现一个Graph类,支持addEdge(u, v)方法添加一条无向边,以及isConnected(u, v)方法查询两个节点是否在同一连通分量中。使用并查集可以高效地支持这两种操作。

示例

输入:n = 5, addEdge(0,1), addEdge(2,3), isConnected(0,1) → true, isConnected(0,2) → false
输出:true, false
solution.ts
输出结果
点击「运行代码」按钮查看结果...