题解：P11812 [PA 2015] 精确打击 / Kontrmanifestacja

· · 题解

原问题有一个等价问题：求这张图上所有点，使得删去这个点，图是一个 DAG。这可以看做原问题的第二定义，这个定义可以帮助我们找到一些性质和写对拍暴力。

(upd 20250301:补充一个忘写的定义) 我们称，如果一个点删去后原图成为 DAG，那么这个点就是 Dagless 的。

首先对原图缩点。缩完之后若干 SCC 之间构成一张 DAG，一个平凡的结论是如果一个 SCC 的大小大于等于 2 ，那么这个 SCC 内必然存在一个环。所以如果存在 2 个及以上的大 SCC，那就意味着存在不交的环，那么无解。所以必然只有一个 SCC，并且其他点对答案不影响，可以删去，后文钦定 “原图是 SCC” 这个条件。

考虑 dfs 树。我们发现所有返边的交必然是一个链，而且最后的答案一定在这个链上。后文我们将寻找一些必要条件，寻求更好的性质。

引理：任何一个环至少要经过一个返祖边

证明：考虑 dfs 树的后序遍历，容易发现只有返祖边会使得后序遍历的序数变大。

那么我们有了这个引理，联系 back 数组，那么对于一个“可选点” x 子树内仍然有“可选点” y 的情况，上面那个点必然 back_x = 0，那么如果一个环必然经过他，则他的后继中还是需要有链上的点，因为根据 back 的定义，不经过链上的点他无法来到一个返祖边。然后根据 jump 的定义，他不可能在任何时候跨过 y，所以这个环必然经过 y。

那么答案具有单调性，二分检测即可，O(n\log n)

进一步的做法

能否做到线性？答案是能。

我们直接对最深的那个 "可选点" 检测一下，如果这个点不合法则这个图不是 Dagless 的。否则我们把这个点拆成 2 个点 S,T，S 继承所有出度，T 继承所有入度。那么一个环对应这个 DAG 是一个从 S\to T 的路径。一个 O(n\alpha(n)) 的做法是直接对这个图跑支配树，就能扫出来 S\to T 的必经点（显然这就是支配树的定义），另一个更为巧妙的做法是把这张图看成无向的跑割点。因为 Dagless 的一定是割点，同时割点一定是 Dagless 的，所以是充要的。复杂度 O(n)。

简要流程汇总

考虑 dfs 树。

1、求返边交。

2、每个点跑最深的可达。

3、找最早的可以到返边。

4、对最后一个判定 Dagless。

5、把最后一个拆点跑无向图割点。

丑陋的赛时代码：

/* Code by pp_orange */
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define m_p(a,b) make_pair(a,b)
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7FFFFFFF
#define inff 9223372036854775807
#define rep(i,l,r) for(int i=l;i<r;++i)
#define repp(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r-1;i>=l;--i)
#define pper(i,r,l) for(int i=r;i>=l;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define p_q priority_queue
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define lb(x) ((x)&-(x))
#define lg(x) (31^__builtin_clz(x))
#define vi vector<int>
#define vii vector<pii >
#define vT vector<T>
#define mm1 mint(1)
const int mod = 998244353;
//#define int ll
const int intsz = sizeof(int);
using namespace std;
inline int rd(){
    int x(0),f(1);char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
inline void out(int X){
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) out(X/10);
    putchar(X%10+'0');
}
ll pw(ll x,int d){
    ll t = 1;
    for(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod;
    return t;
}
#define MAX 500005
vector<int> v[MAX];
vector<int> iv[MAX];
int jump[MAX],back[MAX];
int deg[MAX],ideg[MAX];
bool ban[MAX];
bool cyc[MAX];
int tot,pre[MAX],pa[MAX];
bool vis[MAX];
bool instk[MAX];
// backp[MAX];
int dfn[MAX],idfn[MAX];
int dfnt;
int banpre[MAX];
bool backp[MAX];
bool ans[MAX];
void dfs(int x){
    dfn[x] = ++dfnt;
    idfn[dfnt] = x;
    instk[x] = 1;
    for(auto to : v[x]){
        if(!dfn[to]){
            pa[to] = x;
            dfs(to);
            pre[x] += pre[to];
        }else if(instk[to]){
            backp[x] = 1;
            tot++;
            pre[x]++;
            pre[pa[to]]--;
        }
    }
    instk[x] = 0;
    return ;
}
int tong[MAX];
namespace Tarjan{
    int stk[MAX],tl;
    int dfn[MAX],dfnt,low[MAX];
    void tarjan(int x){
        dfn[x] = low[x] = ++dfnt;
        stk[++tl] = x;
        rep(o,0,2){
            vector<int> &G = o==0?v[x]:iv[x];
            for(auto to : G){
                if(!dfn[to]){
                    tarjan(to);
                    low[x] = min(low[x],low[to]);
                    if(low[to]==dfn[x]){
                        tong[x]++;
                        while(stk[tl]!=x){
                            tong[stk[tl]]++;
                            tl--;
                        }
                    }
                }else{
                    low[x] = min(low[x],dfn[to]);
                }
            }
        }
    }
}
signed main(){
    //freopen("F.in","r",stdin);
    //freopen("F.out","w",stdout);
    int n = rd();
    int m = rd();
    repp(i,1,m){
        int x = rd();
        int y = rd();
        v[x].pb(y);
        iv[y].pb(x);
        deg[y]++;
        ideg[x]++;
    }
    queue<int> q;
    int cnt = 0;
    repp(i,1,n)if(!deg[i])q.push(i);
    while(!q.empty()){
        int x = q.front();q.pop();
        ban[x] = 1;
        cnt++;
        for(auto to : v[x])if(!--deg[to])q.push(to);
    }
    if(cnt==n){
        cout<<"NIE"<<endl;
        return 0;
    }
    repp(i,1,n){
        if(ban[i])continue ;
        if(!ideg[i])q.push(i);
    }
    while(!q.empty()){
        int x = q.front();q.pop();
        ban[x] = 1;
        for(auto to : iv[x]){
            if(ban[to])continue;
            if(!--ideg[to])q.push(to);
        }
    }
    repp(i,1,n){
        if(ban[i]){
            v[i].clear();
            iv[i].clear();
        }
        vector<int> tmp;
        for(auto to : v[i])if(!ban[to])tmp.pb(to);
        v[i] = tmp;
        tmp.clear();
        for(auto to : iv[i])if(!ban[to])tmp.pb(to);
        iv[i] = tmp;
    }
    int st = -1;
    repp(i,1,n){
        if(!ban[i]){
            st = i;
            break ;
        }
    }
    assert(st!=-1);
    dfs(st);
    repp(i,1,n)cyc[i] = (tot==pre[i]);
    // repp(i,1,n)cout<<pa[i]<<' ';cout<<endl;
    // repp(i,1,n)cout<<cyc[i]<<' ';cout<<endl;

    memset(deg,0,sizeof(deg));
    int res = 0;
    repp(i,1,n){
        if(ban[i])continue ;
        if(cyc[i])continue ;
        res++;
        for(auto to : iv[i])if(!cyc[to])deg[to]++;
    }
    // repp(i,1,n)cout<<deg[i]<<' ';cout<<endl;
    // cout<<"res = "<<res<<endl;
    assert(q.empty());
    repp(i,1,n){
        if(ban[i])continue ;
        if(cyc[i])continue ;
        if(!deg[i])q.push(i);
    }
    // cout<<q.size()<<endl;
    vector<int> ord;
    while(!q.empty()){
        int x = q.front();q.pop();
        ord.pb(x);
        res--;
        for(auto to : iv[x]){
            if(cyc[to])continue ;
            if(!--deg[to])q.push(to);
        }
    }
    if(res){
        // cout<<"here"<<endl;
        cout<<0<<endl;
        cout<<endl;
        return 0;
    }
    vector<int> cycver;
    repp(i,1,n)if(cyc[i])cycver.pb(i);
    sort(all(cycver),[&](int x,int y){return dfn[x]>dfn[y];});
    for(auto x : cycver)jump[x] = dfn[x];
    repp(i,1,n){
        if(ban[i])continue ;
        if(!cyc[i]){
            back[i] = backp[i];
        }
    }
    // cout<<"? "<<back[3]<<endl;
    for(auto x : ord){
        for(auto to : v[x]){
            back[x] |= back[to];
            jump[x] = max(jump[x],jump[to]);
        }
    }
    for(auto x : cycver){
        for(auto to : v[x]){
            if(cyc[to]){
                if(pa[to]!=x)jump[x] = max(jump[x],dfn[to]);
                continue ;
            }
            back[x] |= back[to];
            jump[x] = max(jump[x],jump[to]);
        }
        int to = idfn[jump[x]];
        if(to!=x){
            banpre[x]--;
            banpre[pa[to]]++;
        }

    }
    for(auto x : cycver)banpre[pa[x]] += banpre[x];
    vector<int> recyc = cycver;
    reverse(all(recyc));
    back[pa[recyc[0]]] = 0;
    for(auto x : recyc)back[x] |= back[pa[x]];

    // repp(i,1,n)cout<<back[i]<<',';cout<<endl;
    // repp(i,1,n)cout<<banpre[i]<<',';cout<<endl;

    int g = -1;
    for(auto x : cycver){
        if(!back[pa[x]]&&banpre[x]==0){
            g = x;
            break ;
        }
    }
    // cout<<"g = "<<g<<endl;
    assert(g!=-1);
    if(g==-1){
        cout<<0<<endl;
        cout<<endl;
        return 0;
    }
    int S = 0,T = n+1;
    for(auto to : v[g])v[S].pb(to),iv[to].pb(S);;
    for(auto to : iv[g])v[to].pb(T),iv[T].pb(to);
    repp(i,1,n){
        v[i].erase(remove(all(v[i]),g),v[i].end());
        iv[i].erase(remove(all(iv[i]),g),iv[i].end());
    }
    // cout<<"g = "<<g<<endl;
    ban[g] = 1;
    memset(deg,0,sizeof(deg));
    res = 0;
    repp(i,0,n+1){
        if(ban[i])continue ;
        res++;
        for(auto to : v[i])deg[to]++;
    }
    // repp(i,0,n+1)cout<<deg[i]<<' ';cout<<endl;
    assert(q.empty());
    repp(i,0,n+1){
        if(ban[i])continue;
        if(deg[i]==0)q.push(i);
    }
    assert(q.size()==1);
    while(!q.empty()){
        int x = q.front();q.pop();
        res--;
        for(auto to : v[x])if(!--deg[to])q.push(to);
    }
    if(res){
        cout<<0<<endl;
        cout<<endl;
        return 0;
    }
    ans[g] = 1;
    Tarjan::tarjan(0);
    assert(Tarjan::tl==1);
    repp(i,1,n){
        if(ban[i])continue ;
        assert(tong[i]==1||tong[i]==2);
        if(tong[i]==2)ans[i] = 1;
    }
    int anscnt = 0;
    repp(i,1,n)anscnt += ans[i];
    cout<<anscnt<<endl;
    repp(i,1,n)if(ans[i])cout<<i<<' ';
    cout<<endl;
    return 0;
}
/*
g++ F.cpp -o F -g -std=c++14 -Wall -Wshadow -fsanitize=undefined,address && ./F < in.in
ulimit -s unlimited
*/