[题解] CF1019C Sergey's Problem

· · 题解

题意

有一张有向图，构造一个点集，使得点集中的点两两之间没有边，且点集外的任意一点均可以由点集中的点在两步内到达。

\left|V\right|,\left|E\right|\le 10^6

分析

小清新构造题。

第一眼看上去有个很显然是假的贪心，每次随便选择一个点 v，然后删掉所有 v 所有相邻的顶点。这样可以得到 V 的一个点集 V^{\prime} 使得 V 中任意一点可以由 V^{\prime} 中的点在一步内到达。

这是错的是因为某一次选择的点 v_0 可能有一个相邻的点 u_0 是已经被选择的，三元环就是一个反例。

我们观察上面选出来的这个点集 V^{\prime} 有什么特点。

可以发现 G 中 V^{\prime} 的诱导子图 G^{\prime}\left(V^{\prime},E^{\prime}\right)是一个 DAG

对于 E^{\prime} 中任意一条边 u\rightarrow v ，v 在上面贪心过程中被“选择”的时刻严格小于 u 的时刻，否则在 u 被选择后 v 作为 u 的相邻节点就会立刻被删除。

所以 G^{\prime} 中不存在环，即为一个 DAG 。此时我们再在这个图上面按拓扑序跑一边贪心算法，得到 V^{\prime} 的一个子集 V_0 ，此时 V_0 中任意两点间一定没有边，且 V^{\prime} 中任意一点可以由 V_0 中的点在一步内到达。

因此 V_0 是一个符合原题的点集。

Code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <vector>
#include <queue>
using namespace std;
constexpr int N=1000010;
vector<int> es[N],ans;
#define pb emplace_back
namespace fr{
    #include <ctype.h>
    char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
    // #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    // #define putchar(c) (((O==obuf+(1<<23))?(fwrite(obuf,1,O-obuf,stdout),O=obuf):O),*O++=(c))
    template<class T> void rd(T &x){
        T ret=0;bool flg=false;char c=getchar();while(!isdigit(c) && c!='-') c=getchar();
        if(c=='-') c=getchar(),flg=true;while(isdigit(c)) ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
        if(flg) x=-ret;else x=ret;
    }
    void pc(char c){putchar(c);}
    template<class T>
    void wr(T x){
        if(x<0) putchar('-');if(x==0) putchar('0');
        static int cnt,stk[110];cnt=0;
        while(x) stk[++cnt]=x%10,x/=10;
        for(int i=cnt;i;--i)
            putchar(stk[i]+'0');
    }
    void flush(){fwrite(obuf,1,O-obuf,stdout),O=obuf;}
}
using fr::rd;
using fr::pc;
using fr::wr;
using fr::flush;
int n,m,d[N],conn[N];bool del[N],chs[N];
int main(){
    int n,m;rd(n),rd(m);
    for(int i=1,a,b;i<=m;++i){
        scanf("%d%d",&a,&b);
        es[a].pb(b);
    }
    for(int i=1;i<=n;++i) if(!del[i]){
        del[i]=true;chs[i]=true;
        for(int v:es[i])
            del[v]=true;
    }
    for(int i=1;i<=n;++i) if(chs[i])
        for(int v:es[i]) if(chs[v])
            ++d[v];
    queue<int> q;
    for(int i=1;i<=n;++i) if(chs[i] && !d[i])
        q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        if(!conn[u]) ans.pb(u);
        for(int v:es[u]) if(chs[v]){
            conn[v]|=(conn[u]^1);
            if(!(--d[v])) q.push(v);
        }
    }
    wr((int)ans.size());pc('\n');
    for(int v:ans)
        wr(v),pc(' ');
    pc('\n');flush();
    return 0;
}