题目概述

给出一张 $n$ 个点 $m$ 条有向边的图，可以有环但没有自环。现在要选出一个集合 $Q$ 使得 $Q$ 内的点不连通，但 $Q$ 到其他不在 $Q$ 内点的距离( $Q$ 内所有点到该点距离的最小值)都不超过 $2$ 。

解题报告

其实我是在Copy翻译。我们随便删去一个点 $A$ 和他连出去的点，假设删去之后的图的解为 $M$ ，如果 $M$ 能连到 $A$ 那么 $M$ 也是原图的解，否则加入 $A$ ，就是原图的解。这样说明一定有解。

那么我们可以这么构造答案：先按照 $1\sim n$ 的顺序能加就加点，加入点之后把该点连出去的点删掉。这样可以保证没有 $i\to j(i<j)$ 这样的边，同时保证到没选的点的距离不会超过 $1$ 。

但是这样可能会有 $j\to i(i<j)$ 这样的边，现在要做的就是考虑当前解 $M$ 是否能够加入某些点。按照 $n\sim 1$ 的顺序考虑之前被选到的点，如果 $M$ 与该点不连通，那么加入该点。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000,maxm=1000000;

int n,m,ans;bool chk[maxn+5],vis[maxn+5],chs[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y);
    for (int i=1;i<=n;i++)
        if (!vis[i]) {chk[i]=true;for (int j=lnk[i];j;j=nxt[j]) vis[son[j]]=true;}
    memset(vis,0,sizeof(vis));
    for (int i=n;i;i--)
        if (chk[i]&&!vis[i]) {chs[i]=true;ans++;for (int j=lnk[i];j;j=nxt[j]) vis[son[j]]=true;}
    printf("%d\n",ans);for (int i=1,fr=true;i<=n;i++) if (chs[i]) {if (!fr) putchar(' ');fr=false;printf("%d",i);}
    return puts(""),0;
}