CF1019C Sergey's problem (图上构造)

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

思路很清奇

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

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

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

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

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

 1 #include <set>
 2 #include <queue>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define N 1000100
 7 #define ll long long
 8 using namespace std;
 9 //re
10 int gint()
11 {
12     int ret=0,fh=1;char c=getchar();
13     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
14     while(c>='0'&c<='9'){ret=ret*10+c-'0';c=getchar();}
15     return ret*fh;
16 }
17 int n,m,K,ma,cte,num;
18 int head[N],vis[N],use[N];
19 struct Edge{int to,nxt,val;}edge[N*2];
20 void ae(int u,int v){
21     cte++;edge[cte].to=v;
22     edge[cte].nxt=head[u],head[u]=cte;}
23 
24 int main()
25 {
26     freopen("a.in","r",stdin);
27     scanf("%d%d",&n,&m);
28     int x,y,z,fx;
29     for(int i=1;i<=m;i++)
30         x=gint(),y=gint(),ae(x,y);
31     for(int i=1;i<=n;i++)
32         if(!vis[i])
33         {
34             vis[i]=use[i]=1;
35             for(int j=head[i];j;j=edge[j].nxt){
36                 int v=edge[j].to;
37                 vis[v]=1;
38             }
39         }
40     int ans=0;
41     for(int i=n;i>=1;i--)
42         if(use[i])
43         {
44             for(int j=head[i];j;j=edge[j].nxt){
45                 int v=edge[j].to;
46                 use[v]=0;
47             }ans++;
48         }
49     printf("%d
",ans);
50     for(int i=1;i<=n;i++)
51         if(use[i]) printf("%d ",i);
52     puts("");
53     return 0;
54 }