SP131 SQDANCE - Square dance 什么破翻译 & 超水蓝

1234567890sjx · 2023-09-04 09:07:00 · 题解

upd：更新时间复杂度的分析。

题目实际上是这样的：有一个无向图 G，一开始没有边。现在每一次给定一个二元组 (x,y)，如果在图中加入一条 x\to y 的边不会形成环，那么就加入这一条边。问到最后有多少条边没有加入这个无向图 G。

因为要动态维护（加边）点的连通性，所以考虑使用并查集。

对于每一个给定的二元组 (x,y)，如果满足 x 在并查集上的祖先和 y 在并查集上的祖先是同一个祖先，那么加入 x\to y 的边就会形成一个环。否则就一定不会形成一个环，更新并查集。

时间复杂度是 O(\alpha n) 的。

造福后人：数据保证 1\le x,y\le 10^5。