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

· · 题解

Solution

如果整张图已经是 DAG 了，输出 NIE。

那么一个点在所有回路上的充要条件是，删掉他之后图是一张 DAG。不过如果你做了这样的转化，你很大概率是写不出一些正经做法的。原因在于，DAG 的结构太过复杂，没有非常优秀的处理方法。

我们可以找到一个环。显然答案只能是这个环上的节点。

如果删掉这个环之后不是 DAG，那么至少有两个无交环，答案是空集。

否则，所有可能的回路都形如：从环上的一个点出发，走外层 DAG，回到环上的另一个点。

稍微画个图：

加上环上两点 S 和 T，存在一条路径满足，首尾分别是 S 和 T，且中间不经过环上任意元素，则 S\to T 在环上的路径中除了 S 和 T 以外的节点都不会在回路的交上。（注意，S=T 可能发生，这代表有一个只经过 S 的回路。）

如果能把所有的 (S,T) 找出来，我们已经能找到一个必要条件了。

下面证明：如果一个点不会被任何一个类似的 S \to T 覆盖，那么他是合法的。

这个实际上相当简单。因为此时任何一个回路，都不可能跨过该点，必须直接走过去。

假设环上的点编号是 1 到 k。

对于 S 而说，我们可以通过 DAG 上记忆化搜索求出最大的 T 使得 S \to T 路径存在，以及最小的 T 使得 S \to T 的路径存在。

如果 T_{\max} \ge S，显然让 (S,T_{\max}) 中所有元素都不合法即可。

如果 T_{\min} \le S，则设 T_0 为 \le S 且能由 S 到达的最大的节点，则 (S,k] \cup [1,T_0) 都不合法。

可惜我们不太好找 T_0。不过把整张图反过来，通过 T_0 找 S 即可。（注：对于 S 而言，如果 T_{\min} \le S，我们将 (S,k] 记为不合法。而 [1,T_0) 这一段通过枚举 T_0 判断是否有 S 进行判定。）

使用前缀和维护不合法的标记。

复杂度 O(n+m)（如果实现不好，会在输出的时候带 \log，只需要把最终的排序改成桶排就可以做到严格线性了。/tuu）

挺可爱的代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,m,vis[MAXN],pre[MAXN],ok[MAXN];
vector<int> G[MAXN],g[MAXN];
vector<int> cir;
void dfs(int u,int rt) {
    vis[u]=1;
    for(auto v:G[u]) {
        if(v==rt) {
            int tmp=u;
            while(tmp!=rt) cir.push_back(tmp),tmp=pre[tmp];
            cir.push_back(rt);
            reverse(cir.begin(),cir.end());
            return ;
        }
        if(vis[v]) continue ;
        pre[v]=u,dfs(v,rt);
        if(!cir.empty()) return ;
    }
    return ;
}
//=====tarjan=====
int dfn[MAXN],low[MAXN],in[MAXN],tot;
int col[MAXN],cs,ccnt[MAXN];
stack<int> st;
void tarjan(int u) {
    dfn[u]=low[u]=++tot,in[u]=1,st.push(u); 
    for(auto v:G[u]) if(!ok[v]) {
        if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if(in[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        ++cs,ccnt[cs]=0;
        while(1) {
            int v=st.top();
            st.pop();
            col[v]=cs,ccnt[cs]++,in[v]=0;
            if(u==v) return ;
        }
    }
    return ;
}
//====tarjan=====
int prex[MAXN];
void del(int l,int r) {
    l=max(1,l),r=min((int)cir.size(),r);
    if(l>r) return ;
    prex[l]++,prex[r+1]--;
    return ;
}
int mx[MAXN],mn[MAXN];
void solve1(int u) {
    if(vis[u]) return ;
    vis[u]=1;
    if(ok[u]) return mx[u]=mn[u]=ok[u],void();
    mx[u]=0,mn[u]=n+1;
    for(auto v:G[u]) {
        solve1(v);
        mx[u]=max(mx[u],mx[v]);
        mn[u]=min(mn[u],mn[v]);
    }
    return ;
}
void solve2(int u) {
    if(vis[u]) return ;
    vis[u]=1;
    if(ok[u]) return mx[u]=mn[u]=ok[u],void();
    mx[u]=0,mn[u]=n+1;
    for(auto v:g[u]) {
        solve2(v);
        mx[u]=max(mx[u],mx[v]);
        mn[u]=min(mn[u],mn[v]);
    }
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ffor(i,1,m) {int u,v;cin>>u>>v,G[u].push_back(v),g[v].push_back(u);}
    ffor(i,1,n) if(!dfn[i]) tarjan(i);
    int rt=-1;
    ffor(i,1,n) if(ccnt[col[i]]>1) rt=i;
    if(rt==-1) return cout<<"NIE",0;
    dfs(rt,rt);
    ffor(i,0,cir.size()-1) ok[cir[i]]=i+1;

    tot=0,cs=0;
    ffor(i,1,n) dfn[i]=low[i]=col[i]=0;
    ffor(i,1,n) if(!ok[i]&&!dfn[i]) tarjan(i);
    ffor(i,1,n) if(!ok[i]&&ccnt[col[i]]>1) return cout<<0<<'\n',0;

    memset(vis,0,sizeof(vis));
    for(auto id:cir) {
        for(auto to:G[id]) {
            solve1(to);
            if(mx[to]&&mx[to]>=ok[id]) del(ok[id]+1,mx[to]-1);
            if(mn[to]!=n+1&&mn[to]<=ok[id]) del(ok[id]+1,cir.size());
        }
    }
    memset(vis,0,sizeof(vis));
    for(auto id:cir) {
        for(auto to:g[id]) {
            solve2(to);
            if(mx[to]&&mx[to]>=ok[id]) del(1,ok[id]-1);
        }
    }

    ffor(i,1,cir.size()) prex[i]+=prex[i-1];
    vector<int> ans;
    ffor(i,1,cir.size()) if(!prex[i]) ans.push_back(cir[i-1]);
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(auto id:ans) cout<<id<<' ';
    return 0;
}