K - Birdwatching GYM102501（dfs）

本文主要是介绍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;
}

这篇关于K - Birdwatching GYM102501（dfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---