Skip to content

连通块

L2-025 分而治之
L2-013 红色警报

题目大意:给定一个连通块,删去部分节点/边后,连通块的连通性(有几个连通块)

思路1:BFD/DFS 使用搜索搜当前有多少个连通块(利用st[]数组,数修改后的连通块)

思路2:并查集,把构造最开始连通块的边保存(ve),保存删去的节点,根据删去的节点判断ve[i]是否存在,使用并查集将剩下的节点合并。(直接构造修改后的连通块)