拓扑排序总结(Kahn算法)

随便记录点东西

在拓扑排序中，排序结果唯一当且仅当所有顶点间具有全序关系。
快速排序不是稳定的（偏序关系），因为相同元素之间的关系无法确定。
插入排序是稳定的（全序关系），因为相同元素可以通过位置的先后增加关系。
检测某DAG是否为全序关系，只需先进行拓扑排序，再检测结果中所有相邻顶点是否有一致的关系，若都存在正确的关系，则为全序（即此图存在哈密顿路径）。
正如下面的伪码，如果跑了一遍Kahn后还有点没有排好序，那么说明出现了环，即这个这不是个DAG。

Kahn算法

复杂度 O(E+V)
以下例题均采用此方法，并且此方法可以判断是否为DAG。

HDOJ 4857 逃生

反向建边，倒着排好顺序，再逆向输出
排序的过程考虑：若某个点之前没有其他可以加入的点了，就将这个点加入ans队列中。
放入队列q中即意味着放入ans序列了。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

const int maxn=100005;

int n, m;
priority_queue<int> q;  // 序号大的排在前面
vector<int> mp[maxn]; //图
int pre[maxn]; //表示某个点前面有几个必须在此点之前先加入的点
int ans[maxn]; //答案顺序的逆向

void order() {
    int i, cnt=0;;
    for(int i=1; i<=n; ++i) if(pre[i]==0) q.push(i);//若确认此点前面没有pre的点，则可以放入ans了
    memset(ans,0,sizeof(ans));
    while(!q.empty()) {
        int now=q.top(); q.pop();
        ans[cnt++]=now;
        for(int i=0; i<mp[now].size(); ++i) {
            int v=mp[now][i];
            pre[v]--;
            if(!pre[v]) q.push(v);
        }
    }
    for(int i=cnt-1; i; --i) printf("%d ", ans[i]);
    printf("%d\n", ans[0]);
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--) {
        cin>>n>>m;
        memset(pre,0,sizeof(pre));
        for(int i=1; i<=n; ++i) mp[i].clear();
        while(m--) {
            int a, b;
            cin>>a>>b;
            mp[b].push_back(a); //反向建边
            pre[a]++;
        }
        order();
    }
    return 0;
}

HDOJ 1285 确定比赛名次

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

const int maxn=505;

int n, m;
priority_queue<int,vector<int>, greater<int> > q;
vector<int> mp[maxn];
bool vis[maxn][maxn];  //防止某些边出现两次
int pre[maxn];
int ans[maxn];

void order() {
    int cnt=0;
    for(int i=1; i<=n; ++i) if(pre[i]==0) q.push(i);
    memset(ans,0,sizeof(ans));
    while(!q.empty()) {
        int now=q.top(); q.pop();
        ans[cnt++]=now;
        for(int i=0; i<mp[now].size(); ++i) {
            int v=mp[now][i];
            pre[v]--;
            if(!pre[v]) q.push(v);
        }
    }
    for(int i=0; i<cnt-1; ++i) printf("%d ", ans[i]);
    printf("%d\n", ans[cnt-1]);
}

int main() {
    ios::sync_with_stdio(false);
    while(cin>>n>>m) {
        memset(pre,0,sizeof(pre));
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; ++i) mp[i].clear();
        while(m--) {
            int a, b;
            cin>>a>>b;
            if(!vis[a][b]) {
                mp[a].push_back(b);
                pre[b]++;
                vis[a][b]=1;
            }
        }
        order();
    }
    return 0;
}

HDU 1811 Rank of Tetris(并查集+拓扑排序)

这题想了好一会才想到把相等的点进行并查集缩点，并且缩点时顺便取最小的编号代表缩点后的点。
然后就是拓扑排序时如果排了一遍后还有点没有排好，即代码中的cur<N，则说明出现了环。
最后是判断DAG是否为全序关系，利用相邻点的关系是否存在进行判断。