B3644 家谱树

览遍千秋 · 2022-08-16 18:57:09 · 题解

对于第 i 个人的后代 a_{i,j}，我们可以使用图上的有向边来描述这样的后代关系。

建立有向边 i \rightarrow a_{i,j}，表示 a_{i,j} 是 i 的后代。

这样，所有 N 个人的后代关系构成了一个 DAG（有向无环图）。

如果存在边 u \rightarrow v，那么 u 必须在 v 之前输出，自然可以想到拓扑排序 toposort。

输出这张图的一个拓扑序即可。

queue <int> Q;
void toposort() {
    for(int i = 1; i <= n; i++) {
        if(deg[i] == 0) {
            printf("%d ", i);
            Q.push(i);
        }
    }
    while(Q.size()) {
        int x = Q.front(); Q.pop();
        for(int i = Head[x]; i; i = Next[i]) {
            deg[to[i]]--;
            if(deg[to[i]] == 0) {
                printf("%d ", to[i]);
                Q.push(to[i]);
            }
        }
    }
}