题解：P11674 [USACO25JAN] Reachable Pairs G

__cstdio__cpp · 2025-02-04 10:10:00 · 题解

假设某一时刻有 k 个连通块，第 i 个连通块大小为 siz_i ，则问题的答案 Ans= \sum _ {i=1}^k \frac {siz_i (siz_i-1)}{2}

不难发现，操作二并不会改变图的连通性，因此对答案没有贡献，可以直接忽略。

对于操作一，删点操作较难维护。因此可以转化为倒序加点操作，使用并查集维护连通块的合并即可。