洛谷 B3644. 家谱树

问题描述

link

分析

略

参考代码

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

const int N = 1e5 + 10;
int head[N], e[N], ne[N], idx;
int n, m, d[N], q[N];

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

void topsort() {
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
			q[++tt] = i;
		}
	}

	while (hh <= tt) {
		int t = q[hh++];
		for (int i = head[t]; i != -1; i = ne[i]) {
			int j = e[i];
			d[j]--;
			if (!d[j]) {
				q[++tt] = j;
			}
		}
	}

	for (int i = 0; i < hh; i++) {
		cout << q[i] << " ";
	}
}

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

	topsort();

	return 0;
}