自动搬运

查看原文

来自洛谷，原作者为

	K0stlin LIFE IS A CIRCLE.

搬运于2025-08-24 22:23:01，当前版本为作者最后更新于2022-11-18 10:45:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种更好写的方法。

首先我们观察到一个性质：题目中的操作等价于将一个点大于某个儿子的儿子们赋给这个儿子（这里的儿子表示这个点有出边连向的点）。你发现把这些儿子全都赋给当前最小的儿子也是正确的，因为这样儿子集合一定会遍历完。

然后我们只需做到将一个点的儿子集合合并到另一个儿子上，我们可以用 set 启发式合并来维护，具体看代码。

Code( $O(n\log n)$ )：

int n,m;
set<int> S[N];
int main() {
    n=read();m=read();
    for(int i=1,x,y;i<=m;++i) {
        x=read();y=read();
        S[x].insert(y);
    }
    ll ans=0;
    for(int i=1,pos;i<=n;++i) {
        if(S[i].empty()) continue;
        S[i].erase(i);
        ans+=S[i].size();
        pos=(*S[i].begin());
        if(S[i].size()>S[pos].size()) 
            swap(S[i],S[pos]);
        while(!S[i].empty()) {
            S[pos].insert(*S[i].begin());
            S[i].erase(S[i].begin());
        }
    }
    printf("%lld\n",ans);
    return 0;
}