拓扑排序总结(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是否为全序关系，利用相邻点的关系是否存在进行判断。

#include "bits/stdc++.h"

using namespace std;

const int maxn = 1e4+10;

struct Edge{
    int u, v;
    Edge(int u=0, int v=0):u(u),v(v) {}
}edge[2*maxn]; // 记录边

int N, M;
vector<int> g[maxn];
int in[maxn], ans[maxn], fat[maxn], cur, tot, cnt; // 入度，排序结果，并查集父节点，排序成功的顶点数，非等的边数，缩点后的顶点数
int id[maxn]; //缩点后顶点的编号，即belong数组，这里换了个名字

void init() {
    memset(in,0,sizeof(in));
    memset(ans,0,sizeof(ans));
    for(int i=0; i<N; ++i) g[i].clear();
    for(int i=0; i<N; ++i) fat[i]=i;
    tot=cnt=0;
}

int find(int a) { return a==fat[a]?a:find(fat[a]); }
void link(int a, int b) { //并查集
    int x=find(a);
    int y=find(b);
    if(x!=y) {
        int m=min(x,y);
        fat[a]=fat[b]=fat[x]=fat[y]=m; //这里保存最小编号
    }
}

bool solve() {
    priority_queue<int> q;
    cur=0;
    for(int i=N-1; i>=0; --i) if(!in[i]) q.push(i), ans[cur++]=i;
    while(q.size()) {
        int now=q.top(); q.pop();
        for(int i=0; i<g[now].size(); ++i) {
            int v=g[now][i];
            in[v]--;
            if(!in[v]) q.push(v), ans[cur++]=v;
        }
    }
    if(cur<N) return 0; //判断是否所有顶点都已排序，即判断是否有环（是否是DAG）
    return 1;
}

int main() {
    while(cin>>N>>M) {
        init();
        for(int i=0; i<M; ++i) {
            int u, v;
            char c;
            scanf("%d %c %d", &u, &c, &v);
            if(c=='>') edge[tot++]=Edge(u,v); //把边先给记录好，后面还要用
            else if(c=='<') edge[tot++]=Edge(v,u);
            else if(c=='=') link(u,v); //缩点
        }
        for(int i=0; i<N; ++i) {
            if(fat[i]==i) id[i]=cnt++;
            else id[i]=id[find(i)];
        } //得到缩点后编号
        N=cnt; //这里把N改成了cnt，也可以不改
        for(int i=0; i<tot; ++i) {
            int u=edge[i].u;
            int v=edge[i].v;
            g[id[u]].push_back(id[v]);
            in[id[v]]++; //利用记录的边统计入度
        }
        if(!solve()) printf("CONFLICT\n");
        else {
            bool f=1;
            for(int i=0; i<N-1; ++i) { //检查是否所有相邻顶点都有确定的关系，即检查是否为全序DAG
                bool f1=0;
                for(int j=0; j<g[ans[i]].size(); ++j) {
                    int v=g[ans[i]][j];
                    if(v==ans[i+1]) {
                        f1=1;
                        break;
                    }
                }
                if(!f1) {
                    f=0;
                    break;
                }
            }
            if(f) printf("OK\n");
            else printf("UNCERTAIN\n");
        }
    }
}