拓扑排序 / Top Sort

作用：对图进行排序

如在上图中，对每个结点进行排序，使在排序后的列表 a a a 中满足 i < j i < j i

2 , 4 , 5 , 3 , 1 2, 4, 5, 3, 1 2,4,5,3,1 即为一种合法排列，
而 2 , 4 , 3 , 5 , 1 2, 4, 3, 5, 1 2,4,3,5,1 不是，因为 3 3 3 是 5 5 5 的子节点。

1. 记录每一个节点的入度；

2. 查找入度为 0 0 0 的节点，加入队列；

3. 从队列中取出一项，加入到答案列表，并遍历这一项的子节点，执行第 4 , 5 4, 5 4,5 步，如果队列不为空，重新执行第 3 3 3 步，否则结束排序。

4. “剪掉” 当前节点与子节点的路线；

5. 如果这个子节点的新入度为 0 0 0，加入到队列中。

如上图，遍历顺序为:

队列: 2 | 4 | 5   | 3     | 1       |
答案:   | 2 | 2 4 | 2 4 5 | 2 4 5 3 | 2 4 5 3 1

如图：(绿色代表入度数量，红色箭头代表正在判断的节点编号)

Example：一本通1351-家谱树

变量用途：

const int N = 1100;
int idx, ver[N], nxt[N], hd[N], d[N];
std::vector v;
// idx -> 存储当前边数      | ver -> 存储边的终点
// nxt & hd -> 用于遍历图  | d -> 存储边的入度数量
// v -> 存储答案 

重点: 拓扑排序算法：

void top_sort() {
    std::queue q;
    for (int i = 1; i <= n; i++) if (!d[i]) q.push(i); // 步骤 2
    while (q.size()) { // 步骤 3-3: 如果 q 为空跳出循环
        int a = q.front(); // 步骤 3-1: 从队列中取出一项，加入到答案列表
        v.push_back(a);
        q.pop();
        for (int i = hd[a]; i; i = nxt[i]) { // 步骤 3-2: 遍历这一项的子节点
            int y = ver[i];
            d[y]--; // 步骤 4
            if (!d[y]) q.push(y); // 步骤 5
        }
    }
}

主函数：

int n, k;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        while (scanf("%d", &k)) {
            if (!k) break; // 如果 k 为 0 代表该行结束
            add(i, k); // 把边 i -> k 添加如列表
            d[k]++; // 点 k 的入度加 1
        }
    }
    top_sort(); // 进行拓扑排序
    for (int i : v) printf("%d ", i); // 输出结果
    return 0;
}

入度 代表终点为这个点的边的数量