核心思路

    对于DAG（有向无环图）的有序序列，每次应找到所有入度为零的点存入队列，并将该点的出度清空（“剪断”对应的边）；易知，最终队列中元素出现的次数为n时，拓扑排序完成，否则图中一定出现了环.
    PS:拓扑序列并不唯一

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
auto toposort=[&]() -> bool
{
    queue<int>q;
    int tot = 0;
    for(int i = 1; i <= n; i++)
        if(!in[i])
            q.push(i),tot++;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(auto it:e[temp]){
            in[it]--;
            if(!in[it])
                q.push(it),tot++;
        }
    }
    return tot==n;
}

思考变式

求字典序最大的拓扑序列

▶　Code: 
auto toposort=[&]() -> bool
{
    priority_queue<int> q; //通过优先队列高效实现对拓扑序列的最值筛选
    int tot = 0;
    for(int i = 1;i <= n;i++)
        if(!in[i])
            q.push(i),tot++;
    while(!q.empty()){
        int temp=q.top();
        q.pop();
        for(auto it:e[temp]){
            in[it]--;
            if(!in[it])
                q.push(it),tot++;
        }
    }
    return tot==n;
}