CF1019C Sergey's problem (图上构造)

题目大意：给你一个有向连通图，让你找出一个点集，保证点集内的点之间没有直接连边，且集合中存在一点，到一个 非点集中的点的距离小于等于2

思路很清奇

首先编号从小到大遍历每个点，如果这个点没有被访问过，把它加入集合中，再把和它的出边连接的点都标记为访问过，

如此做，会发现集合内的点到集合外的点距离最大是1

但这样做就会不满足条件1，因为是有向图，已经在集合内的点中，编号大的点可能会指向编号小的点

再按编号倒序遍历集合中的点，如果它指向了一个编号较小的，且在集合中的点，那么把那个点从集合中删除

这样做，会发现集合内的点到集合外的点距离最大是2，且集合内的点没有直接连边，答案合法

 #include <set>

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 1000100

 #define ll long long

 using namespace std;

 //re

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,m,K,ma,cte,num;

 int head[N],vis[N],use[N];

 struct Edge{int to,nxt,val;}edge[N*];

 void ae(int u,int v){

     cte++;edge[cte].to=v;

     edge[cte].nxt=head[u],head[u]=cte;}

 int main()

 {

     freopen("a.in","r",stdin);

     scanf("%d%d",&n,&m);

     int x,y,z,fx;

     for(int i=;i<=m;i++)

         x=gint(),y=gint(),ae(x,y);

     for(int i=;i<=n;i++)

         if(!vis[i])

         {

             vis[i]=use[i]=;

             for(int j=head[i];j;j=edge[j].nxt){

                 int v=edge[j].to;

                 vis[v]=;

             }

         }

     int ans=;

     for(int i=n;i>=;i--)

         if(use[i])

         {

             for(int j=head[i];j;j=edge[j].nxt){

                 int v=edge[j].to;

                 use[v]=;

             }ans++;

         }

     printf("%d\n",ans);

     for(int i=;i<=n;i++)

         if(use[i]) printf("%d ",i);

     puts("");

     return ;

 }