题解：P9469 [EGOI 2023] Sopsug / 垃圾处理

· · 题解

先把显然不合法的判掉了：好边出度 >1，成环。

有好边出度的点已经不能再往外连了，考虑保留好边森林中的每个树根。考虑先暴力找树根可以向其它树根连的无向边，显然这样的无向边是非常多的，于是每次和连通块连通成功后就启发式合并并且不再尝试和该连通块中的其他点连边。这样做的复杂度是 O(n\log n+k) 的，第一项复杂度显然是由于启发式合并，第二项是因为成功合并次数 <n，失败次数 <2k。

剩下的连通块数是 O(k^{\frac12}) 的，因为这些连通块两两之间至少有一条坏边阻隔。考虑此时只能从每个根往不同块的任意节点连有向边，于是尝试往每个连通块连边，连边成功后就不再连边。这样做的复杂度是 O(k^{\frac32}) 的，因为每个无好边出度点至多向每个连通块连一条边，且失败次数 <2k。

最后直接枚举每个连通块的任一个树根作为根是否可行，显然也是 O(k^{\frac32}) 的。

复杂度 O(n\log n+m+k^{\frac32})。精细实现一下，例如强制每两个连通块之间只连一条边并在最后使用 Tarjan 缩点检查，就可以做到 O(n\log n+m+k^{\frac32})。

#include<bits/stdc++.h>
using namespace std;

namespace leo{

constexpr int N=300005;
typedef pair<int,int>pii;
#define FI first
#define SE second

int n,m,k,vis[N],rt[N];
vector<int>g[N],ts[N],ig3[N];
vector<pii>G[N],iG[N];
unordered_set<int>g2[N];
unordered_set<int>s[N];
set<int>active;
int bel[N];
vector<pii>es,es2;
vector<pii>res;
int ind[N];

int merge(int u,int v){
    if(s[u].size()<=s[v].size())swap(u,v);
    for(int x:s[v]){
        bel[x]=u;
        s[u].insert(x);
    }
    s[v].clear();
    return v;
}

void dfs(int u){
    for(pii e:iG[u])
        if(!~vis[e.FI]){
            vis[e.FI]=e.SE;
            dfs(e.FI);
        }
}

void dfsig3(int u){
    vis[u]=1;
    for(int v:ig3[u])
        if(!vis[v]){
            res.push_back({v,u});
            dfsig3(v);
        }
}

void solve(){
    cin>>n>>m>>k;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;u++,v++;
        g[u].push_back(v);
        res.push_back({u,v});
    }
    for(int i=1,u,v;i<=k;i++){
        cin>>u>>v;u++,v++;
        g2[u].insert(v);
    }
    for(int i=1;i<=n;i++){
        if(g[i].size()>1u){
            cout<<"NO"<<endl;
            return;
        }
    }
    for(int i=1;i<=n;i++){
        int u=i,t=0;
        while(!vis[u]){
            vis[u]=i;
            if(g[u].size())u=g[u][0];
            else{t=u,u=0;break;}
        }
        if(vis[u]==i){
            cout<<"NO"<<endl;
            return;
        }
        if(!t)t=rt[vis[u]];
        rt[i]=t;ts[t].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(g[i].size())continue;
        bel[i]=i;
        s[i].insert(i);
        active.insert(i);
    }
    for(int i=1;i<=n;i++){
        if(g[i].size())continue;
        vector<int>del;
        for(int u:active){
            if(u==bel[i])continue;
            for(int v:s[u]){
                if(g2[i].find(v)==g2[i].end()&&
                    g2[v].find(i)==g2[v].end()){
                        es.push_back({i,v});
                        ig3[v].push_back(i);
                        ig3[i].push_back(v);
                        del.push_back(merge(bel[i],u));
                        break;
                    }
            }
        }
        for(int u:del)active.erase(u);
    }
    for(int i=1;i<=n;i++){
        if(g[i].size())continue;
        for(int u:active){
            if(u==bel[i])continue;
            for(int p:s[u])for(int v:ts[p]){
                if(g2[i].find(v)==g2[i].end()){
                    G[bel[i]].push_back({u,(int)es2.size()});
                    iG[u].push_back({bel[i],(int)es2.size()});
                    es2.push_back({i,v});
                    goto O;
                }
            }O:;
        }
    }
    int RT=0;
    vector<int>rts;
    for(int u:active){
        for(int v:active)vis[v]=-1;
        vis[u]=0;dfs(u);
        int f=1;
        for(int v:active)if(!~vis[v])f=0;
        if(!f)continue;
        RT=u;
        for(int v:active)if(v!=u){
            res.push_back(es2[vis[v]]);
            rts.push_back(es2[vis[v]].FI);
        }
        rts.push_back(u);
        break;
    }
    if(!RT){
        cout<<"NO"<<endl;
        return;
    }
    memset(vis,0,sizeof(vis));
    for(int u:rts){
        dfsig3(u);
    }
    for(pii e:res)cout<<e.FI-1<<' '<<e.SE-1<<'\n';
}

}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    leo::solve();
}