家谱树

原题链接

题目描述

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。

给出每个人的孩子的信息。

输出一个序列，使得每个人的孩子都比那个人后列出。

---

拓扑排序

模板题。

代码

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

const int N = 110, M = N * N;

int n;
int h[N], e[M], ne[M], idx;
int d[N];
vector<int> v;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);

    while (q.size()) {
        int u = q.front();
        q.pop();

        v.push_back(u);

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q.push(j);
        }
    }
}

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

    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        while (cin >> x, x) {
            add(i, x);
            d[x]++;
        }
    }

    topsort();

    for (int it : v) cout << it << ' ';

    return 0;
}