B3644

佬头 · 2023-11-10 10:50:07 · 题解

Description

给出每个人后代的信息。输出一个序列，使得每个人的后辈都在那个人后面。

Solution

拓扑序列

• 对一个有向无环图（DAG）进行拓扑排序，就是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 u\to v\in E(G)，则 u 在线性序列中出现在 v 之前。通常我们称这个序列为拓扑序列，序列中顶点的顺序是拓扑序。

我们用 son_i 表示 i 的晚辈，cnt_i 表示 i 的长辈的个数，显然一定 \exists~i\le n,~cnt_i=0（不然就不是 DAG 了，可以思考一下为什么。每个人都有自己的父亲？我的父亲是我的晚辈？）。

接下来我们把 cnt=0 的人从 DAG 中除去，显然他们没有长辈，不需要在任何人后面。除去的同时我们将其晚辈的 cnt 自减，如果变成了 0，就代表他的这个晚辈因此而没有长辈了，就把那个晚辈也除去。通过上述方式求出来额就是拓扑序列了。

由于同一时刻会有很多人满足 cnt=0，因此我们需要一个 queue 来维护他们。时间复杂度 \mathcal O(n)。

Code

#include <iostream>
#include <vector>
using namespace std;
const int N = 102;
int n, q[N], back, cnt[N];
vector <int> son[N];
int read(){
    int x = 0;
    char a = getchar();
    while(a < '0' || '9' < a) a = getchar();
    while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
    return x;
}
void write(int x){
    if(x > 9) write(x / 10);
    putchar(x % 10 | 48);
}
int main(){
    n = read();
    for(int i = 1; i <= n; ++ i)
        for(int a = read(); a; a = read())
            son[i].push_back(a), ++ cnt[a];
    for(int i = 1; i <= n; ++ i) if(!cnt[i]) q[++ back] = i, write(i), putchar(' ');
    for(int front = 1; front <= back; ++ front)
        for(int i: son[q[front]])
            if(!-- cnt[i])
                q[++ back] = i, write(i), putchar(' ');
    return 0;
}

strengthen

P7860 [COCI2015-2016#2] ARTUR