K - Birdwatching GYM102501（dfs）

题意： 给定一个特定点，求有多少个点能到达该特定点，且只能通过与该点直接相连的点到达

思路：
对于所有与特定点直接相连的点设为集和S，如果存在点 a∈S，使得a能到达b∈S，则a不是所求点。

我们去掉与特定点直接相连的边，其他边建立反图，再对集和S中的点跑dfs，判断有多少个点能到达自己。如果S中的点遍历到的点的个数大于二（除了自己还有S中其他点），则说明还有其他边到达特定点。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
 
using namespace std;
 
const int maxn = 2e5 + 7;
int head[maxn],nex[maxn],to[maxn],tot;
vector<int>a,ans;
set<int>f[maxn];
 
void add(int x,int y) {
    to[++tot] = y;
    nex[tot] = head[x];
    head[x] = tot;
}
 
void dfs(int x,int root) { //计算有多少个点可以被root到达，每个点最多被遍历两次
    if(f[x].size() > 1 || f[x].count(root)) return;
    f[x].insert(root);
    for(int i = head[x];i;i = nex[i]) {
        int v = to[i];
        dfs(v,root);
    }
}
 
int main() {
    int n,m,t;scanf("%d%d%d",&n,&m,&t);
    for(int i = 1;i <= m;i++) {
        int x,y;scanf("%d%d",&x,&y);
        if(y == t) {
            a.push_back(x);
            continue;
        }
        add(y,x);
    }
    
    for(int i = 0;i < a.size();i++) {
        dfs(a[i],a[i]);
    }
    
    for(int i = 0;i < a.size();i++) {
        if(f[a[i]].size() == 1) {
            ans.push_back(a[i]);
        }
    }
    
    sort(ans.begin(),ans.end());
    printf("%d\n",ans.size());
    for(int i = 0;i < ans.size();i++) {
        printf("%d\n",ans[i]);
    }
    return 0;
}