计算连通块数量有一个经典的公式:
连通块数量=点数−边数在这个问题中,我们要求的是活跃连通区域的数量,所以公式可以相应地调整为:
在一个星际传送网络中,有 n 个节点和 n−1 条双向通道,节点编号为 1 到 n。该网络保证任意两个节点之间都存在唯一一条不重复经过节点的通路,并且不存在环路。初始时所有节点均为休眠状态。现在进行 q 次操作,每次给定两个节点 u 和 v,将二者唯一通路上的所有节点激活。请你求出全部操作结束后,激活节点形成的活跃连通区域数量。
【名词解释】
约束:节点总数 n 和操作次数 q 均不超过 2 * 10^5;节点编号在 1 到 n 之间;每条通道连接的两个节点编号不同;操作中的两个节点可以相同。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.