反向建边+记忆化
查看原帖
反向建边+记忆化
436516
to_be_N0_1楼主2021/8/30 21:43

这做法哪有错啊,反向建边然后直接记忆化,直接一开始先让有牛的场地为1,然后dfs!!!

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int cnt[N];
vector<int>v[N];
int vis[N];
void dfs(int u){
    vis[u] = 1;
    for(int v : v[u]){
		if(!vis[v]) dfs(v);
  		cnt[u] += cnt[v];
    }
}
int a[N];
int main(){
    //fio;
    int k, n, m; cin >> k >> n >> m;
    int val;
    for(int i = 1; i <= k; ++i) cin >> val, cnt[val]++;
    for(int i = 1; i <= m; ++i){
        int u, vv; cin >> u >> vv;
        v[vv].push_back(u);
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(!vis[i]) dfs(i);
        if(cnt[i] == k) ++ans;
    }
    cout << ans << endl;
    return 0;
}
2021/8/30 21:43
加载中...