题意：
给你一个无向图，和一个关键点T，问你有哪些点Ti不经过边Ti->T就到不了T？
边数点数<=1e5
练习的时候队友都说没看懂，打完听孟神复述了题意，我：？？？
这个题目很奇怪哦，看上去挺反直觉的，但是确实是河里的
那么遇到有向图，常见技巧，建反向边
这道题建立反向边的好处是把问题转化为从T出发，不经过T->Ti就到不了的Ti有多少个，把多起点转化为单起点，更易于思考
一个朴素的想法是分别以每个有从T->Ti边的Ti作为起点进行bfs，然后统计哪些点经过一次，但这样复杂度O(n^2)，会被菊花图或水母图卡
接着发现性质：
对于满足题目要求的一个Ti，只能从唯一的一个和T相邻的点出发访问到（否则就不满足条件了）
那么每个点至多只有必要被两次bfs访问，第三次访问到的时候，由于bfs的特点，此点后面的所有点也都至少访问了两次，这些点都已经从答案中被排除掉了，因此不必再遍历一次
那么时间复杂度就优化到了O(n)
细节：
如果Ti不存在T->Ti的边，那么即使只用一种方法从T到Ti，也不能被算作答案，样例很良心，包含了这种情况
要判断这个情况也非常好处理，如果某个Ti只存在一种方法从T到Ti，那么只要存在边T-Ti，这一定就是唯一的方法
因此和T连边的点，和只存在一次bfs访问的点取交集就是答案
这题确实挺简单的，但是队友没看懂，就没想，果然看题还是十分重要的啊
代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 struct edg{int nxt,y;}e[110000]; int lk[110000],ltp=0; 5 void ist(int x,int y){ 6 e[++ltp]=(edg){lk[x],y}; lk[x]=ltp; 7 } 8 int n,m,o; 9 int f[110000]; 10 int g[110000]; 11 int q[110000],hd=0; 12 void bfs(int x){ 13 if(g[x]>1) return ; 14 q[hd=1]=x; 15 f[x]=1; 16 g[x]++; 17 for(int k=1;k<=hd;++k){ 18 for(int i=lk[q[k]];i;i=e[i].nxt){ 19 if(g[e[i].y]==2) continue; 20 if(f[e[i].y]==1) continue; 21 f[e[i].y]=1; 22 g[e[i].y]++; 23 q[++hd]=e[i].y; 24 } 25 } 26 for(int k=1;k<=hd;++k) 27 f[q[k]]=0; 28 } 29 void prvs(){ 30 for(int i=0;i<=n;++i) lk[i]=0; 31 ltp=0; 32 for(int i=0;i<=n;++i){ 33 f[i]=0; 34 g[i]=0; 35 } 36 } 37 int main(){ 38 while(scanf("%d%d%d",&n,&m,&o)!=EOF){ 39 prvs(); 40 int l,r; 41 while(m --> 0){ 42 scanf("%d%d",&l,&r); 43 ist(r,l); 44 } 45 g[o]=2; 46 for(int i=lk[o];i;i=e[i].nxt) 47 bfs(e[i].y); 48 for(int i=lk[o];i;i=e[i].nxt) 49 f[e[i].y]=1; 50 int cnt=0; 51 for(int i=0;i<=n;++i)if(g[i]==1 && f[i]==1) 52 ++cnt; 53 printf("%d ",cnt); 54 for(int i=0;i<=n;++i)if(g[i]==1 && f[i]==1) 55 printf("%d ",i); 56 } 57 return 0; 58 }