P8907 题解

EXODUS · 2022-12-25 22:10:52 · 题解

Part 1：前言

谢谢这道题让我意识到我在启发式合并方面一窍不通。

感觉这是 Pt 组最简单的一题

Part 2：正文

考虑一个性质，每次互相连边显然有些多余，不妨转化成将编号最小的点和其它点连边。

考虑正确性，若一头牛 x 出队，不妨设与他相连且编号大于他的牛的编号排序后的结果为 y_1,y_2,...,y_k，我们这种连边策略相当于延时连边，即在 y_1 出队以前连接 y_1\rightarrow y_2,y_3,\ldots y_k，y_2 出队以前连接 y_2\rightarrow y_3,\ldots y_k，每条应当连的边都被连上了至少一次，故存在充分性，所以正确。

直接连边复杂度是 O(n^2)，启发式合并 set 后复杂度是 O(m\log^2n) 可以通过此题。

Part 3：代码

const int N=2e5+7;
int n,m;
set<int>g[N];

void Main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        g[min(u,v)].insert(max(u,v));
    }
    ll ans=-m;
    for(int i=1;i<=n;i++){
        if(g[i].empty())continue;
        ans+=g[i].size();
        int u=*g[i].begin(),v=i;g[v].erase(g[v].begin());
        if(g[u].size()<g[v].size())swap(g[u],g[v]);
        for(auto i:g[v])g[u].insert(i);
    }
    cout<<ans;
    return;
}