洛谷 P2853 [USACO06DEC] Cow Picnic S

// ★★ P2853 正解：**从每头牛出发各搜一次**，给走到的牧场计数；数满 K 次的就是答案。
//
// 反过来想是错的（见 p2853Rev.cpp）：题目问「哪些牧场**所有牛都到得了**」，
// 而「牛 c 到得了哪些牧场」正是一次从 c 出发的 DFS。
//
//     for (每头牛 c) { 清空 vis；从 c 的牧场 DFS；每碰到一个牧场 cnt[v]++ }
//     答案 = #{ v : cnt[v] == K }
//
// ⚠ 两头牛可能在**同一个牧场**，那就从那个牧场搜两次 —— cnt 照样各加一次，`== K` 仍然对。
//
// 复杂度 O(K(N + M))：顶格 100 × (1000 + 10000) = **1.1 × 10⁶**。
// ★★ 而同一份算法换成邻接矩阵存图就是 O(KN²) = **10⁸**（见 p2853Mat.cpp）——
//   这道题是[第 29 章](/ch/29-graph-storage/)「三种存法实测比一比」最干净的场子。

#include <bits/stdc++.h>
using namespace std;

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

    int K, n, m;
    if (!(cin >> K >> n >> m)) return 0;              // ⚠ 第一行是 K N M，别读反
    vector<int> cow(K);
    for (int i = 0; i < K; i++) cin >> cow[i];
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);                            // ★ 单向路，只存一遍
    }

    vector<int> cnt(n + 1, 0), st;
    vector<char> vis(n + 1);
    for (int c : cow) {
        fill(vis.begin(), vis.end(), 0);              // ★★ 每头牛都要从头再来
        st.clear(); st.push_back(c); vis[c] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            cnt[u]++;
            for (int v : g[u]) if (!vis[v]) { vis[v] = 1; st.push_back(v); }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (cnt[i] == K) ans++;
    printf("%d\n", ans);
    return 0;
}

// ⚠ P2853：同一个算法，存法换成**邻接矩阵** —— 答案一个字都不错，复杂度从 O(K(N+M)) 变成 O(KN²)。
//
// 矩阵版找「u 的邻居」要把整整一行 n 个格子扫一遍，不管 u 有几条出边。
// ⇒ 顶格 K = 100、N = 1000：**10⁸** 次，而邻接表只要 1.1 × 10⁶ —— 差约 **90 倍**。
//
// ★★ 顺带回答一件[正文第 9 步](/ch/29-graph-storage/)留下的事：
//   `char` 矩阵**记不住重边**。可这道题只问「到不到得了」，
//   **它丢掉的那部分信息，这道题根本不问** ⇒ 矩阵版在这里是**完全正确**的。
//   ⇒ 「存法丢信息」和「这道题会不会被坑」是两句话。
//
// ⚠ 命令行给一个 `count` 参数，它就只打「一共看了多少个格子 / 多少条边」。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    bool countOnly = (argc > 1 && string(argv[1]) == "count");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K, n, m;
    if (!(cin >> K >> n >> m)) return 0;
    vector<int> cow(K);
    for (int i = 0; i < K; i++) cin >> cow[i];
    vector<vector<char>> a(n + 1, vector<char>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;                                  // ★ 重边在这里被合并了（这道题不在乎）
    }

    vector<int> cnt(n + 1, 0), st;
    vector<char> vis(n + 1);
    long long looks = 0;
    for (int c : cow) {
        fill(vis.begin(), vis.end(), 0);
        st.clear(); st.push_back(c); vis[c] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            cnt[u]++;
            for (int v = 1; v <= n; v++) {            // ★ 整整一行，n 个格子
                looks++;
                if (a[u][v] && !vis[v]) { vis[v] = 1; st.push_back(v); }
            }
        }
    }
    if (countOnly) { printf("%lld\n", looks); return 0; }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (cnt[i] == K) ans++;
    printf("%d\n", ans);
    return 0;
}

// ✗ P2853 错法一：`vis` 数组**只清了一次**（放在了循环外面）。
//
// 于是第二头牛开始，凡是上一头牛走过的牧场都被当成「已经访问过」直接跳过 ——
// cnt 再也加不上去。表现是**答案偏小**（多半直接是 0）。
//
// ★ 恒 ≤ 正解：漏计不会凭空多出可达关系。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int K, n, m;
    if (!(cin >> K >> n >> m)) return 0;
    vector<int> cow(K);
    for (int i = 0; i < K; i++) cin >> cow[i];
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; g[a].push_back(b); }

    vector<int> cnt(n + 1, 0), st;
    vector<char> vis(n + 1, 0);                       // ★ 清空只发生在这里
    for (int c : cow) {
        if (vis[c]) continue;
        st.clear(); st.push_back(c); vis[c] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            cnt[u]++;
            for (int v : g[u]) if (!vis[v]) { vis[v] = 1; st.push_back(v); }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (cnt[i] == K) ans++;
    printf("%d\n", ans);
    return 0;
}

// ✗ P2853 错法二：**方向反了** —— 建反图，从每头牛出发。
//
// 反图上「从牛 c 走得到 v」= 原图上「**v 走得到 c**」。
// ⇒ 它算的是「**能到达所有牛**的牧场有几个」，而题目问的是「**所有牛都到得了**的牧场」。
//
// ★★ 说清楚它算了什么之后，一切都是白送的推论：
//   在**每条边都双向**的图上两者一模一样（那时原图 = 反图），
//   而这道题的路是**单向**的（题面第一句就写着 one-way paths）⇒ 它错。
//
// ⚠ 上一道 [P3916](/sol/p3916/) 的正解**正是**「反向建图」，这道题反过来就错 ——
//   [「上一道题的正确写法就是这一道题的 bug」](/sol/p1171/) 在同一张题单里又一次。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int K, n, m;
    if (!(cin >> K >> n >> m)) return 0;
    vector<int> cow(K);
    for (int i = 0; i < K; i++) cin >> cow[i];
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; g[b].push_back(a); }   // ★ 反着存

    vector<int> cnt(n + 1, 0), st;
    vector<char> vis(n + 1);
    for (int c : cow) {
        fill(vis.begin(), vis.end(), 0);
        st.clear(); st.push_back(c); vis[c] = 1;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            cnt[u]++;
            for (int v : g[u]) if (!vis[v]) { vis[v] = 1; st.push_back(v); }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (cnt[i] == K) ans++;
    printf("%d\n", ans);
    return 0;
}