HBC235366[SDOI2008]校门外的区间,线段树,数据结构Connect Graph题解

天涯离梦残月幽梦算法基础篇 2023-11-22 10:35:01 119 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

条边的无向图，现在要在这个图上按顺序添加。条无向边，每新添加一条边需要花费。1天时间，问每个点最早何时与。条边，加入第一条边的时间为第一天，若加入第。i 条边之后某个点与。1号点不联通，则称该点与点

有一个 n n 个点， m_1 m 1 条边的无向图，现在要在这个图上按顺序添加 m_2 m 2 条无向边，每新添加一条边需要花费 1 1 天时间，问每个点最早何时与 1 1 号点联通。注：以未加“之后的 m_2 m 2 条边”时作为第 0 天，即第 0 天时图上就有 m_1 m 1 条边，加入第一条边的时间为第一天，若加入第 i i 条边之后某个点与 1 1 号点联通，且在此之前该点与 1 1 号点不联通，则称该点与点 1 1 联通的时间为 i i。