dfs, but 10pts
查看原帖
dfs, but 10pts
1350908
gjrBJ楼主2025/6/14 13:30

思路就是枚举每个点作为野餐地点然后dfs求能到达该点的奶牛数量

#include<bits/stdc++.h>
using namespace std;
int k, n, m, a, b, x, ans, anss, vis[1010], f[100010];
vector<int> v[100010], v1[100010];
void dfs(int num) {
    if (f[num] >= 1) {
        ans += f[num];
        return ;
    }
    for (auto x : v1[num]) {
        if (!vis[x]) {
            vis[x] = 1;
            dfs(x);
        }
    }
}
int main() {
    cin >> k >> n >> m;
    for (int i = 1; i <= k; i++) {
        cin >> x;
        f[x]++;
    }
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v1[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        ans = f[i];
        vis[i] = 1;
        dfs(i);
        if (ans == k) {
            anss++;
        }
    }
    cout << anss;
    return 0;
}
2025/6/14 13:30
加载中...