洛谷 B3644 【模板】拓扑排序 / 家谱树

// ★ B3644 正解：Kahn 算法（入度 + 队列）—— 本章 fast.cpp 原样搬过来，只换了读入。
//
// 题面：给每个人的**后代**列表（以 0 结尾），要求「每个人的后辈都比那个人后列出」
// ⇒ 一条「i 是 j 的长辈」的关系就是一条有向边 `i → j` ⇒ 求任意一个拓扑序。
//
// ⚠⚠ 这道题**答案不唯一**（题面明写「如果有多种不同的序列，输出任意一种即可」）——
//   于是对拍**不能逐字节比**。本页的办法是写一个**验证器**（b3644Check.cpp），
//   只问「你给的这个顺序合不合法」。解析页第 ③ 步说了这件事值多少。
//
// ⚠ 读入是**变长行**：`后代… 0`。和 [P1113](/sol/p1113/) 一样，别去管换行，
//   直接把整个输入当一条数字流读到 0 为止。
//
// 复杂度 O(n + m)。题面 n ≤ 100，随便写。

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

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

    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) { g[i].push_back(v); indeg[v]++; }
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i);   // ★ 所有入度为 0 的点，一个都不能少
    string out;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (!out.empty()) out += ' ';
        out += to_string(u);
        for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
    }
    out += '\n';
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

// ⚠ B3644：把 Kahn 里的**队列换成栈** —— 看着像 bug，其实**一次都不会错**。
//
// 「先进先出」换成「后进先出」，输出的顺序当场就变了（样例上 `2 4 5 3 1` 变成别的）。
// 可拓扑排序**从来没要求过顺序**：Kahn 的正确性只依赖一件事 ——
// **一个点被输出时，它的所有前驱都已经输出过了**。而「从哪个容器里挑下一个」
// 对这件事毫无影响，挑谁都行。
//
// ⇒ ★★ 所以这一版**答案不同、但同样合法**。300 轮验证器全过（解析页第 ③ 步）。
//   ⚠ 而如果拿它去和正解**逐字节比**，会报一大堆「不一致」—— 那全是假阳性。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) { g[i].push_back(v); indeg[v]++; }
    }
    vector<int> st;
    for (int i = 1; i <= n; i++) if (!indeg[i]) st.push_back(i);
    string out;
    while (!st.empty()) {
        int u = st.back(); st.pop_back();              // ★ 栈：后进先出
        if (!out.empty()) out += ' ';
        out += to_string(u);
        for (int v : g[u]) if (--indeg[v] == 0) st.push_back(v);
    }
    out += '\n';
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

// ✗ B3644 错法一：**边的方向存反了** —— 把「i 的后代是 j」读成了「j → i」。
//
// 题面那句话要一个字一个字读：「第 i 行描述第 i 个人的**后代**编号」，
// 而输出要求「每个人的**后辈**都比那个人**后**列出」⇒ 边是 `i → j`（长辈指向后辈）。
//
// ★ 说清楚它算了什么：它输出的是**反着的**拓扑序（后辈在前）。
// ⚠ 而这个错法在**每条边上**都错，所以官方样例一测就死。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) { g[v].push_back(i); indeg[i]++; }   // ★ 反了
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) if (!indeg[i]) q.push(i);
    string out;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (!out.empty()) out += ' ';
        out += to_string(u);
        for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
    }
    out += '\n';
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

// ✗ B3644 错法二：**一开始只把 1 号点入队**（忘了「所有入度为 0 的点」）。
//
// Kahn 的第一步是「把**所有**入度为 0 的点放进队列」。只放一个，
// 那些不在 1 号点可达范围里的点就永远出不来 ⇒ **输出的序列短了一截**。
//
// ⚠ 它和第 30 章 [B3625](/sol/b3625/) 第一版那个「只从 1 号点搜」是同一个形状的错 ——
//   **默认「图是从 1 号点连通的」**。题面从来没这么保证过。
// ★ 而这一次验证器能一眼看穿它：长度不是 n。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int v;
        while (cin >> v && v != 0) { g[i].push_back(v); indeg[v]++; }
    }
    queue<int> q;
    if (indeg[1] == 0) q.push(1);                     // ★ 只放 1 号
    string out;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (!out.empty()) out += ' ';
        out += to_string(u);
        for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
    }
    out += '\n';
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}