P11812 [PA 2015] 精确打击 / Kontrmanifestacja

· · 题解

感觉这题并不困难啊。

首先，我们发现这题本质上是在求所有环的交点。

应该可以容易的想到先找出一个主环（至少我很容易就想到了）。

然后我们需要特判一下，如果没环输出 NIE，如果找出一个主环之后，去掉这个环，整个图中还有其他环，那么答案是 0。

接下来这题就一定有解了。

考虑如何求多个环的交点，交集并不好做，考虑把可以不交的点都去掉。

我们对主环上的点重编号成 1 \sim len。

那么我们设 l_i,r_i 表示主环上一点 i 走非主环上的边能到的最小的主环上的点的编号和最大的主环上的点的编号，可以会有如下几种情况。

此处只考虑 i 之后的点的合法性。

我们同样设 mx_i 表示走非主环上的边可以到达主环上的点 i 的编号最大的点，依旧分类讨论。

此处只考虑 i 之前的点的合法性。

正确性应该是显然的。

你考虑怎么求这个东西，可以直接上正反图，跑一下拓扑排序，当然主环上的点会比较特殊。

然后一段区间不能选，可以用差分维护，不能选就区间 +1。

所以最后求一遍前缀和，值为 0 的点就是交点。

按顺序输出即可。

个人认为这题代码难度大于思维难度。

:::success[code]

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x;
}
const int N=1e6+10;
int ans,n,m,cnt,head[N],to[N],nxt[N],fhead[N],fto[N],fnxt[N];
void add(int u,int v){
    ++cnt;
    to[cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
    fto[cnt]=u,fnxt[cnt]=fhead[v],fhead[v]=cnt;
    return ;
}
int top,vis[N],lst[N],stk[N],stkpos[N];
int tot,cycle[N],pos[N],oncycle[N],iscycle[N];
bool dfs(int x){
    vis[x]=1,stk[++top]=x,stkpos[x]=top;
    for(int e=head[x];e;e=nxt[e]){
        int y=to[e];
        if(!vis[y]){
            lst[y]=e;
            if(dfs(y)) return 1; 
        }
        else if(vis[y]==1){
            for(int i=stkpos[y];i<=top;i++){
                cycle[++tot]=stk[i],pos[stk[i]]=tot,oncycle[stk[i]]=1;
                if(i>stkpos[y]) iscycle[lst[stk[i]]]=1;
            }
            iscycle[e]=1;
            return 1;
        }
    }
    vis[x]=2,stkpos[x]=0,top--;
    return 0;
}
int deg[N],q[N];
bool check(){
    for(int i=1;i<=n;i++){
        if(oncycle[i]) continue;
        for(int e=head[i];e;e=nxt[e]) 
            if(!oncycle[to[e]]) deg[to[e]]++;
    }
    int L=1,R=0,num=0;
    for(int i=1;i<=n;i++) if(!oncycle[i]&&!deg[i]) q[++R]=i;
    while(L<=R){
        int x=q[L++];
        num++;
        for(int e=head[x];e;e=nxt[e])
            if(!oncycle[to[e]]&&!(--deg[to[e]])) q[++R]=to[e];
    }
    return num!=n-tot;
}
int d[N];
int l[N],r[N],cl[N],cr[N];
void work1(){
    memset(deg,0,sizeof deg);
    for(int i=1;i<=n;i++)
        for(int e=fhead[i];e;e=fnxt[e])
            if(!iscycle[e]&&!oncycle[fto[e]]) deg[fto[e]]++;
    for(int i=1;i<=tot;i++) l[cycle[i]]=r[cycle[i]]=i;
    int L=1,R=0;
    for(int i=1;i<=n;i++) if(!deg[i]) q[++R]=i;
    while(L<=R){
        int x=q[L++];
        for(int e=fhead[x];e;e=fnxt[e]){
            if(iscycle[e]) continue;
            int y=fto[e];
            if(oncycle[y]){
                if(l[x]){
                    if(!cl[y]) cl[y]=l[x],cr[y]=r[x];
                    else cl[y]=min(cl[y],l[x]),cr[y]=max(cr[y],r[x]);
                } 
            }
            else {
                if(l[x]){
                    if(!l[y]) l[y]=l[x],r[y]=r[x];
                    else l[y]=min(l[x],l[y]),r[y]=max(r[x],r[y]);
                }
                if(!(--deg[y])) q[++R]=y;
            }
        }
    }
    for(int i=1;i<=tot;i++){
        int x=cycle[i];
        if(!cl[x]) continue;
        if(i<cl[x]) d[i+1]++,d[cr[x]]--;
        else d[i+1]++;
    }
    return ;
}
int mx[N],cmx[N];
void work2(){
    memset(deg,0,sizeof deg);
    for(int i=1;i<=n;i++)
        for(int e=head[i];e;e=nxt[e])
            if(!iscycle[e]&&!oncycle[to[e]]) deg[to[e]]++;
    for(int i=1;i<=tot;i++) mx[cycle[i]]=i;
    int L=1,R=0;
    for(int i=1;i<=n;i++) if(!deg[i]) q[++R]=i;
    while(L<=R){
        int x=q[L++];
        for(int e=head[x];e;e=nxt[e]){
            if(iscycle[e]) continue;
            int y=to[e];
            if(oncycle[y]) cmx[y]=max(cmx[y],mx[x]);
            else {
                mx[y]=max(mx[x],mx[y]);
                if(!(--deg[y])) q[++R]=y;
            }
        }
    }
    for(int i=1;i<=tot;i++){
        int x=cycle[i];
        if(cmx[x]>=i) d[1]++,d[i]--;
    }
    return ; 
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++) add(read(),read());
    bool flag=0;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        if(dfs(i)){
            flag=1;
            break;
        }
    }
    if(!flag) cout <<"NIE",exit(0);
    if(check()) cout <<"0",exit(0);
    work1(),work2();
    for(int i=1;i<=tot;i++){
        d[i]+=d[i-1];
        if(!d[i]) ans++;
    }
    cout <<ans<<"\n";
    for(int i=1;i<=n;i++) if(oncycle[i]&&!d[pos[i]]) cout <<i<<" ";
    return 0;
}

:::