洛谷 P2712 摄像头

// ★ P2712 正解：**入度 = 被几个摄像头监视着**，然后 Kahn 一层层剥 —— 剥不掉的就是环里的。
//
// 题意翻译：摄像头 A 监视位置 y；如果 y 正好是摄像头 B 所在的位置，
// 那么**B 必须等 A 被砸了才能砸** ⇒ 连边 A → B，B 的入度 +1。
// ⇒ 能全砸完 ⟺ 这张图无环 ⟺ 拓扑排序能把 n 个点全排出来。
//
// ⇒ ★ 这就是本章那句「判环不用另写一份代码」的直接应用：
//   **队列空了、出队的点却不够 n 个 ⇔ 有环**，而剩下几个就答几个。
//
// ⚠ 三处容易漏的：
//   ① 摄像头监视的位置 y **可能根本没有摄像头** ⇒ 那条信息直接扔掉（`at[y] < 0`）；
//   ② 题面**没有排除自环**（一个摄像头监视自己所在的位置）—— 那它永远砸不掉；
//   ③ ⚠ 题面写着 `0 ≤ x, y ≤ 500` ⇒ **位置编号本来就很小，根本不用离散化**，
//      开一个 501 的数组直接查就行（本章题单原来那句「编号很大要离散化」已订正）。
//
// 复杂度 O(n × m + 值域)。题面 n ≤ 100、m ≤ 100 ⇒ 一万条边，随便跑。

#include <bits/stdc++.h>
using namespace std;
const int V = 501;                                    // 位置编号 0 ~ 500

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> pos(n), at(V, -1);                    // at[p] = 位置 p 上是几号摄像头
    vector<vector<int>> watch(n);
    for (int i = 0; i < n; i++) {
        int x, m;
        cin >> x >> m;
        pos[i] = x;
        at[x] = i;
        watch[i].resize(m);
        for (int& y : watch[i]) cin >> y;
    }

    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < n; i++)
        for (int y : watch[i]) {
            int j = at[y];
            if (j < 0) continue;                      // ① 那个位置没有摄像头，扔掉
            g[i].push_back(j);
            indeg[j]++;                               // ② i == j（自环）也照算，于是它永远砸不掉
        }

    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) if (--indeg[v] == 0) box.push_back(v);
    }
    int left = n - (int)box.size();
    if (left == 0) printf("YES\n");
    else printf("%d\n", left);
    return 0;
}

// ✗ P2712 错法一：**边的方向反了**。
//
// 「摄像头 A 监视着 B 所在的位置」意味着 **B 要等 A 被砸了才能砸** ⇒ 边 `A → B`。
// 反着连就成了「A 等 B」，整张依赖关系倒了个个儿。
//
// ★ 说清楚它算了什么：它解的是**反图**上的同一道题 ——
//   而反图和原图的**环是同一批**（一个环反过来还是环）⇒
//   ⚠ **它对「能不能全砸完」这个是非题永远答得对**，只在「剩几个」上才可能错。
//   解析页第 ④ 步量了这件事。

#include <bits/stdc++.h>
using namespace std;
const int V = 501;                                    // 位置编号 0 ~ 500

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> pos(n), at(V, -1);                    // at[p] = 位置 p 上是几号摄像头
    vector<vector<int>> watch(n);
    for (int i = 0; i < n; i++) {
        int x, m;
        cin >> x >> m;
        pos[i] = x;
        at[x] = i;
        watch[i].resize(m);
        for (int& y : watch[i]) cin >> y;
    }

    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < n; i++)
        for (int y : watch[i]) {
            int j = at[y];
            if (j < 0) continue;                      // ① 那个位置没有摄像头，扔掉
            g[j].push_back(i);                        // ★ 反了
            indeg[i]++;
        }

    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) if (--indeg[v] == 0) box.push_back(v);
    }
    int left = n - (int)box.size();
    if (left == 0) printf("YES\n");
    else printf("%d\n", left);
    return 0;
}

// ✗ P2712 错法二：**顺手把自环跳过了**（`if (i == j) continue;`）。
//
// 一个摄像头如果**监视着自己所在的位置**，它就永远砸不掉（砸它的人会被它拍下来）。
// 题面 `0 ≤ x, y ≤ 500` 从头到尾**没有排除**这种情况。
//
// ⚠⚠ 这和[上一轮 P1330](/sol/p1330/) 那个「跳过自环」是**同一个动作**，
//   而且**同样是题面没排除、生成器又不爱造**的那一类。
//   ⇒ ★★ 连着两轮撞见同一个坑：**「顺手写一句无害的防御」是有代价的，
//     那句 `continue` 到底扔掉了什么，得先问一句。**

#include <bits/stdc++.h>
using namespace std;
const int V = 501;                                    // 位置编号 0 ~ 500

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> pos(n), at(V, -1);                    // at[p] = 位置 p 上是几号摄像头
    vector<vector<int>> watch(n);
    for (int i = 0; i < n; i++) {
        int x, m;
        cin >> x >> m;
        pos[i] = x;
        at[x] = i;
        watch[i].resize(m);
        for (int& y : watch[i]) cin >> y;
    }

    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < n; i++)
        for (int y : watch[i]) {
            int j = at[y];
            if (j < 0) continue;                      // ① 那个位置没有摄像头，扔掉
            if (i == j) continue;                     // ★ 就是这一句
            g[i].push_back(j);
            indeg[j]++;                               // ② i == j（自环）也照算，于是它永远砸不掉
        }

    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) if (--indeg[v] == 0) box.push_back(v);
    }
    int left = n - (int)box.size();
    if (left == 0) printf("YES\n");
    else printf("%d\n", left);
    return 0;
}

// ✗ P2712 错法三：**把「位置编号」直接当成了「摄像头编号」**。
//
// 输入里的 `x`、`y` 是**位置**，而摄像头是按输入顺序 0..n−1 编号的 —— 两套编号。
// 这一版省掉了 `at[]` 这张查找表，直接拿 `y` 当摄像头下标用。
//
// ⚠ 位置编号能到 500 而摄像头只有 100 个 ⇒ 它还会越界；
//   这一版用 `.at()` 把那个 UB 换成确定的异常，好让它真的现形一次。
// ★ 而**当所有摄像头恰好摆在位置 0..n−1 上时，两套编号重合，它就蒙对了** ——
//   解析页第 ④ 步造了这么一档来验这句话。

#include <bits/stdc++.h>
using namespace std;
const int V = 501;                                    // 位置编号 0 ~ 500

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> pos(n), at(V, -1);                    // ★ 这一版根本不用 at[]
    vector<vector<int>> watch(n);
    for (int i = 0; i < n; i++) {
        int x, m;
        cin >> x >> m;
        pos[i] = x;
        at[x] = i;
        watch[i].resize(m);
        for (int& y : watch[i]) cin >> y;
    }

    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < n; i++)
        for (int y : watch[i]) {
            try {
                g.at(i).push_back(y);                 // ★ 直接拿位置编号当摄像头下标
                indeg.at(y)++;
            } catch (const std::out_of_range&) {
                printf("越界了（真机上这里是未定义行为）\n");
                return 0;
            }
        }

    vector<int> box;
    for (int i = 0; i < n; i++) if (!indeg[i]) box.push_back(i);
    size_t head = 0;
    while (head < box.size()) {
        int u = box[head++];
        for (int v : g[u]) if (--indeg[v] == 0) box.push_back(v);
    }
    int left = n - (int)box.size();
    if (left == 0) printf("YES\n");
    else printf("%d\n", left);
    return 0;
}