搜索与图论_拓扑排序

拓扑排序

思路

• 记录各点的入度
• 从度数为零的点开始bfs
• 用队列存储度数变为零的点

代码模板

bool 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 = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if(--d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}