拓扑序

约 309 个字 127 行代码预计阅读时间 3 分钟

在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；

在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。

多种方案，让1尽量靠前，1最靠前的方案里，选择2尽量靠前的方案，满足前两条件的方案里，选择3尽量靠前的方案....

这个限制不是字典序最小，比如下例,解决方法是反向建图，序号大的先出队，答案按照出队逆序输出

input
3 1
3 1
wrong output
2 3 1
true output
3 1 2

删边的实质是让一个点的入度减1，所以删边判环，可以优化为枚举点入度减1再判环

题目¶

确定比赛名次

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 500+5;
const int maxm = maxn * maxn;
// 建图
struct node{
    int to, next;
}edge[maxm];
int head[maxn], cnt;
void add(int u, int v){
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int du[maxn]; // 入度
int n, m;
queue<int> ans; // 获取答案
int topu1(void){
    queue<int> q; // 入度为0的点
    for(int i = 1;i <= n;i++){
        if(du[i] == 0) q.push(i);
    }
    int tot = 0;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        ans.push(now);
        tot++;
        for(int i = head[now];i;i = edge[i].next){ // 遍历这个点所连向的边，把这条边删掉
            int to = edge[i].to;
            du[to]--; // 入度减一
            if(du[to] == 0) q.push(to);
        }
    }
    // 拓扑排序判断是否有环
    if(tot == n) return 1; // 无环
    else return 0; // 有环
}
int topu2(void){
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i = 1;i <= n;i++){
        if(du[i] == 0) q.push(i);
    }
    int tot = 0;
    while(!q.empty()){
        int now = q.top(); // 寻找入度的点里面，值最小的点
        q.pop();
        ans.push(now);
        tot++;
        for(int i = head[now];i;i = edge[i].next){
            int to = edge[i].to;
            du[to]--;
            if(du[to] == 0) q.push(to);
        }
    }
    if(tot == n) return 1;
    else return 0;
}
int main(void){
    while(scanf("%d %d", &n, &m) != EOF){
        memset(du, 0, sizeof(du));
        memset(head, 0, sizeof(head));
        cnt = 0;
        for(int i = 0; i < m;i++){
            int u, v;
            scanf("%d %d", &u, &v);
            add(u, v);
            du[v]++; // v的入度增加
        }
        topu2();
        int flag = 0;
        while(!ans.empty()){
            int now = ans.front();
            ans.pop();
            if(flag) putchar(' ');
            flag = 1;
            printf("%d", now);
        }
        puts("");
    }
    return 0;
}

板子¶

namespace topuSort
{
    queue<int> q;
    int in[N];
    vector<int> e[N];
    int n;
    void init(int nn)
    {
        n=nn;
        memset(in,0,sizeof(int)*(n+1));
        for(int i=1;i<=n;++i)
            e[i].clear();
        while(!q.empty())
            q.pop();
    }
    void addEdge(int u,int v)
    {
        e[u].push_back(v);
        ++in[v];
    }
    bool run()
    {
        for(int i=1;i<=n;++i)
        {
            if(!in[i])
                q.push(i);
        }
        int u,cnt=0;
        while(!q.empty())
        {
            u=q.front();
            q.pop();
            ++cnt;
            for(int v:e[u])
            {
                if(--in[v]==0)
                    q.push(v);
            }
        }
        return cnt==n;
    }
};