P6680 [CCO2019] Marshmallow Molecules

K0stlin · 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;
}