[C++] P2853 [USACO06DEC] Cow Picnic S

发表于 更新于 分类于

K(1 ≤ K ≤ 100) 只奶牛分散在 N(1 ≤ N ≤ 1000) 个牧场．现在她们要集中起来进餐。牧场之间有 M(1 ≤ M ≤ 10000) 条有向路连接，而且不存在起点和终点相同的有向路．她们进餐的地点必须是所有奶牛都可到达的地方。那么，有多少这样的牧场可供进食呢？

输入格式

第 1 行：三个以空格分隔的整数，分别为：K, N, M。

第 2 行到第 K + 1 行：每行包含一个整数 Ci（1 ≤ Ci ≤ N），表示第 i 头奶牛所在的牧场编号。

第 K + 2 行到第 M + K + 1 行：每行包含两个以空格分隔的整数 A 和 B，表示一条从牧场 A 到牧场 B 的单向路径。（1 ≤ A, B ≤ N, A ≠ B）

输出格式

第一行：一个整数，即所有奶牛都可以到达的牧场数量。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
2 4 4
2
3
1 2
1 4
2 3
3 4

输出 #1

1
2

说明/提示

奶牛可以在 3 或 4 号牧场相遇。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <numeric>
using namespace std;

void dfs(int node, bool *visited, vector<int> *farms_routes, int *farms) {
    //cout << "Visiting node: " << node << endl; // Debug statement to track the nodes being visited. Remove in final version.
    visited[node] = true;
    farms[node]++;
    for(auto it : farms_routes[node]){
        if(!visited[it]){
            dfs(it, visited, farms_routes, farms);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k, m;
    cin >> k >> n >> m;

    int cows[k];
    for (int i = 0; i < k; i++) {
        cin >> cows[i];
    }

    vector<int> farm_routes[n];
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        farm_routes[a-1].push_back(b-1);
    }

    int farms[n] = {0};
    bool visited[n] = {false};
    for (int i = 0; i < k; i++) {
        memset(visited, false, sizeof(visited));
        dfs(cows[i]-1, visited, farm_routes, farms);
    }

    // for (int i = 0; i < n; i++)
    // {
    //     cout << farms[i] << " ";
    // }
    
    cout << accumulate(farms, farms+n, 0, [k](int base, int cows){
        return cows==k?base+1:base;
    });

    return 0;
}