https://www.luogu.com.cn/problem/P2853

題目大意

k頭牛在n個點上，m條有向邊，統計那些所有牛都能到達的點的個數

思路

很容易就想到，以每頭牛為起點去深搜，能走到的地方數值加1，最后那些數值為k的點就是所有牛都能走到的點。

ps: 本來還順著這樣想了一個優化，如果在牛 a 的路徑上有另外一頭牛 b，那么 b能走到的路徑必定包含在a能走到的以內，那么我dfs加一個參數num，如果多碰到一頭牛，num++，這樣在牛a的深搜中就把牛b的也走完了，再標記一下后面不用走牛b了，然后走到的點的數值變成加num，深搜完了后再判斷一下恢復num，感覺挺可行的，但是寫出來卻wa了，不知道自己是想法有誤還是代碼敲錯。

以下為ac代碼

代碼

#include <bits/stdc++.h> using namespace std; const int N = 1005;int k, n, m, ans; vector <int> g[N]; vector <int> cow; int flag[N]; int f[N];void dfs(int x) {flag[x] = 1;f[x]++;for (int i = 0; i < g[x].size(); i++) {int fp = 0;if (flag[g[x][i]]) continue;dfs(g[x][i]);}return ; }int main() {cin >> k >> n >> m;for (int i = 0; i < k; i++) {int c; cin >> c;cow.push_back(c);}for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;g[u].push_back(v);}for (int i = 0; i < cow.size(); i++) {memset(flag, 0, sizeof(flag));dfs(cow[i]); }for (int i = 1; i <= n; i++) {if (f[i] == k) ans++;}cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的洛谷 P2853 Cow Picnic S（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。