【Codeforces 1019C】Sergey's problem | Mrsrz's blog

构造。

题目大意：

给定一张有向图，你需要选择一些结点染黑，其他点为白色，并满足条件：

• 黑点之间没有边相连。
• 对于一个白点，存在一个黑点，能在走不超过 22 条边后到达这个白点。

输出一种方案。

题解：

这是一种挺妙的构造方案。

我们定义一个点有一个状态为“被控制的”或者“不被控制的”。

我们按照某种顺序枚举所有点，如果它不是被控制的，则将它染黑，并将它 $1$ 步内能到的点都标记为被控制的。

然后倒序枚举所有点，如果它是黑点，那么把和它相连的黑点变成白色。

剩下的黑点就是满足条件的方案。

为什么这样是对的呢？

考虑 $u\rightarrow v$，且 $u
$ 和 $v$ 都是黑点，那么 $u$ 必然比 $v$ 后染色，否则 $v$ 不可能是黑点。那么在倒序访问的时候，$u$ 一定先被访问到，$v$ 就会被删除。而属于 $v$ 管辖的只是走 $1$ 条边能访问到的点，而 $u$ 到 $v$ 也是一条边，即原来 $v$ 控制的点，现在变成了 $u$ 控制。那么仍然保证所有点都“被控制”。

再考虑 $u\rightarrow v\rightarrow w$，这里 $u$ 肯定会被先访问，那么 $v$ 就没有了，而 $w$ 仍然存在。这样是没有问题的。更长的链也可依此类推。

于是时间复杂度 $O(n+m)$。

Code：

#include<cstdio>
#include<bitset>
using namespace std;
const int N=1e6+5;
struct edge{
    int to,nxt;
}e[N];
int head[N],cnt,n,m;
bool vis[N];
bitset<N>bt;
inline void dfs(int u,int dep){
    vis[u]=1;
    if(dep==1)return;
    for(int i=head[u];i;i=e[i].nxt)if(!vis[e[i].to])dfs(e[i].to,dep+1);
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
    }
    for(int i=1;i<=n;++i)if(!vis[i]){
        vis[i]=bt[i]=1;
        for(int j=head[i];j;j=e[j].nxt)vis[e[j].to]=1;
    }
    for(int i=n;i;--i)if(bt.test(i))for(int j=head[i];j;j=e[j].nxt)bt.reset(e[j].to);
    printf("%d\n",bt.count());
    for(int i=1;i<=n;++i)if(bt.test(i))printf("%d ",i);
    return 0;
}