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

· · 题解

题意简述

给定 n 个结点、m 条必须保留的有向边和 k 条禁止使用的有向边。需要补成一棵所有边都指向根的有根树，或判断无解。

解题思路

先处理必须保留的边。

在一棵所有边指向根的树中，每个结点的出度至多为 1，忽略方向后也不可能出现环。因此，若某个结点有两条必须出边，或者必须边的无向图成环，就一定无解。这两项可以分别用出边数组和并查集检查。

若检查通过，每个必须边连通块都是一棵内向树。设一个连通块有 s 个结点，它恰有 s-1 条边，且每个结点出度至多为 1，所以恰有一个结点出度为 0。称它为块根。

只有块根还能够增加一条出边，其余结点的出边已经由必须边确定。因此可以把每棵内向树收缩成一个组件。

设组件 X 的块根为 r_X。若要让 X 指向另一个组件 Y，只需在 Y 中找到某个结点 u，并加入：

r_X\to u

这条边可用，当且仅当 Y 中至少存在一个结点 u，使有序对 (r_X,u) 不在禁止列表中。

建立组件辅助图，并把上述可用边反向。若 X 可以指向 Y，就在辅助图中加入 Y\to X。原问题有解，当且仅当辅助图中存在一个能到达所有组件的结点。

必要性来自最终树。把最终树的组件间边全部反向后，全局根所在组件可以到达其余所有组件。

反过来，若辅助图中的组件 R 能到达所有组件，就取一棵以 R 为根的遍历树。对遍历树边 Y\to X，选择 Y 中一个允许的结点 u，并在原图加入 r_X\to u。于是每个非根组件都恰有一条边指向其父组件，沿父链最终到达 R。组件内原有边又全部指向块根，所以所有结点最终都到达 R 的块根。所得图连通、无环且恰有 n-1 条边。

辅助图接近完全图，不能显式建边。不过，它的缺边很少。

辅助图中不存在 Y\to X，当且仅当对 Y 的每个结点 u，(r_X,u) 都是禁止边。读入禁止边后，按起点块根和目标组件计数。若计数等于目标组件大小，就记录一条辅助图缺边 Y\not\to X。每条缺边至少对应一条不同的原禁止边，所以辅助图缺边总数不超过 k。

接下来需要在线性规模内遍历这个补图。

用后继并查集维护尚未访问的组件编号。处理组件 Y 时，先临时标记它的全部缺边终点，再从最小的未访问编号开始扫描。未标记的组件可以沿辅助边直接访问，并从后继并查集中永久删除；被标记的组件跳到下一个编号。

一次遍历中，每个成功检查都会删除一个组件。每个失败检查都对应当前组件的一条不同缺边。因此一次完整遍历的复杂度为 O((n+k)\alpha(n))。

还要避免逐个尝试所有组件作为全局根。依次从尚未访问的组件开始遍历，并记录最后一次遍历的起点 R。

若某个组件 Q 能到达所有组件，分两种情况。若遍历曾从 Q 开始，这次遍历会直接结束全部搜索。否则，Q 已被某个更早的起点访问；该起点能先到达 Q，再由 Q 到达所有组件，也会结束全部搜索。因此在存在可行根时，最后一个遍历起点一定也是可行根。

清空访问状态后，再从 R 完整遍历一次。若仍有组件未访问，则无解；否则记录这次遍历树的父组件，用它构造答案。

构造每条新边时，临时标记对应块根的全部禁止终点，再扫描父组件内的结点，取第一个未标记结点。辅助边存在保证一定能够找到。每个组件只构造一次出边，每条禁止边也只会被标记或导致扫描失败常数次。

并查集合并、补图遍历和构造的总时间复杂度为 O((n+m+k)\alpha(n))，空间复杂度为 O(n+m+k)。

参考代码

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

const int N=300005;
int n,m,k,tot,cnt,tim;
int fa[N],siz[N],to[N],id[N],bel[N],rt[N],nxt[N],tag[N],mark[N],num[N],st[N],par[N];
int a[N],b[N],c[N],d[N];
bool vis[N];
vector<int> G[N],B[N],V[N];
int find(int u)
{
    return u==fa[u]?u:fa[u]=find(fa[u]);
}
void merge(int u,int v)
{
    u=find(u);
    v=find(v);
    if(siz[u]<siz[v])swap(u,v);
    fa[v]=u;
    siz[u]+=siz[v];
}
int get(int u)
{
    int v=u;
    while(nxt[v]!=v)v=nxt[v];
    while(nxt[u]!=u)
    {
        int w=nxt[u];
        nxt[u]=v;
        u=w;
    }
    return v;
}
void init()
{
    for(int i=0;i<tot;i++)vis[i]=0;
    for(int i=0;i<=tot;i++)nxt[i]=i;
    cnt=0;
}
void walk(int root,bool save)
{
    vis[root]=1;
    cnt++;
    nxt[root]=get(root+1);
    int top=0;
    st[top++]=root;
    while(top)
    {
        int u=st[--top];
        tim++;
        for(auto v:G[u])tag[v]=tim;
        int v=get(0);
        while(v<tot)
        {
            if(tag[v]==tim)
            {
                v=get(v+1);
                continue;
            }
            vis[v]=1;
            cnt++;
            nxt[v]=get(v+1);
            st[top++]=v;
            if(save)par[v]=u;
            v=get(v);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    fill(to,to+n,-1);
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
        siz[i]=1;
    }
    bool ok=1;
    for(int i=0;i<m;i++)
    {
        cin>>a[i]>>b[i];
        if(to[a[i]]!=-1)ok=0;
        else to[a[i]]=b[i];
        if(find(a[i])==find(b[i]))ok=0;
        else merge(a[i],b[i]);
    }
    for(int i=0;i<k;i++)cin>>c[i]>>d[i];
    if(!ok)
    {
        cout<<"NO"<<'\n';
        return 0;
    }
    fill(id,id+n,-1);
    for(int i=0;i<n;i++)
    {
        if(to[i]!=-1)continue;
        id[find(i)]=tot;
        rt[tot++]=i;
    }
    for(int i=0;i<n;i++)
    {
        bel[i]=id[find(i)];
        V[bel[i]].push_back(i);
    }
    for(int i=0;i<k;i++)
    {
        if(to[c[i]]==-1)B[c[i]].push_back(d[i]);
    }
    for(int i=0;i<tot;i++)
    {
        int x=rt[i];
        int top=0;
        for(auto v:B[x])
        {
            int y=bel[v];
            if(mark[y]!=i+1)
            {
                mark[y]=i+1;
                num[y]=0;
                st[top++]=y;
            }
            num[y]++;
        }
        for(int j=0;j<top;j++)
        {
            int y=st[j];
            int len=V[y].size();
            if(y!=i&&num[y]==len)G[y].push_back(i);
        }
    }
    init();
    int root=-1;
    for(int i=0;i<tot;i++)
    {
        if(vis[i])continue;
        root=i;
        walk(i,0);
    }
    init();
    walk(root,1);
    if(cnt<tot)
    {
        cout<<"NO"<<'\n';
        return 0;
    }
    for(int i=0;i<m;i++)cout<<a[i]<<' '<<b[i]<<'\n';
    for(int i=0;i<tot;i++)
    {
        if(i==root)continue;
        int x=rt[i];
        tim++;
        for(auto v:B[x])tag[v]=tim;
        for(auto v:V[par[i]])
        {
            if(tag[v]==tim)continue;
            cout<<x<<' '<<v<<'\n';
            break;
        }
    }
    return 0;
}