给定一个无向图,节点分为运行(R)和等待(W)两种状态。求将第i个节点强制设为运行状态后,有多少个运行簇。
如果节点原本就是运行状态,将其强制设为运行,运行簇的数量显然不变。
如果节点原本是等待状态,将其强制设为运行,则要取决于与该节点相邻的节点有多少已经是运行状态的。而这些已经是运行状态的节点有可能已经位于同一个运行簇中了,因此我们需要使用并查集来判断它们是否处于同一个集合。
最开始,通过某一个未被标记的运行节点开始遍历,将其所能到达的所有运行节点划分到该集合中,然后标记。重复上述过程,直到所有运行节点都被划分进集合中。此时可以求得集合总数为res,也就是最开始的答案或者说将运行节点强制设为运行的答案。
在一个分布式系统中,有 n 个节点,编号 1 到 n,节点之间通过 m 条双向通信链路相连。每个节点初始处于 运行 (R) 或 等待 (W) 两种状态之一。如果两个运行节点可以通过一系列运行节点相连(即路径上的所有节点均为运行状态),则它们属于同一个 运行簇(即运行节点的连通分量)。
现在需要评估每个节点的重要性:对于每个节点 i,假设将其状态强制设为运行(若原本就是运行则不变),请问此时整个系统中运行簇的数量是多少?请对每个节点输出该数量。
约束
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.