「解题记录」AtCoder Beginner Contest 304 E – Good Graph
题目传送门 题目简述 给定一张无向图和数列 X, Y。 有 K 次询问,每次询问需要判断在询问的 u, v 之间建边之后,判断「对于所有 X_i 和 Y_i 之间都不存在路径」是否成立。 保证原图不存在 X_i, Y_i 之间有路径。 思路分析 容易发现,在同一个连通块中的所有点都存在相互可达的路径。如果新加入的边连接了两个连通块,那么这两个连通块之间的所有点就都存在路径相互可达。 因此,对于每一对 X_i, Y_i,只需判断「新加入的边是否连通了这两个点所在的连通块」。 可以用 map 来实现 […]