拓扑排序

给出一些大小关系，然后求出一个总的大小关系。比如：甲>丙， 丙>乙，可以的到一个大小关系：甲 > 丙 > 乙

模板代码：

void toporder(int n) {
    queue<int>q;
    for (int i = 0; i < n; i++) {
        if (!deg[i]) q.push(i);
        // deg[i] 表示第i个点的度数，这里先把度数为0的点加入队列
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // u是排到的点，这里根据情况写
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            if (!--deg[v]) {
                q.push(v);
            }
        }
    }
}

HRBUST 1631 技能修炼

输出拓扑排序的顺序

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define MEM(a) memset(a,0,sizeof(a))
const int N = 510;
int digree[N];
int path[N];
int G[N][N];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        int u, v;
        MEM(G),MEM(path),MEM(digree);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &u, &v);
            G[u][v] = 1;
            digree[v]++;
        }
        priority_queue<int, vector<int>, greater<int> >q;
        for (int i = 1; i <= n; i++) {
            if (!digree[i]) q.push(i);
        }
        int l = 0;
        while (!q.empty()) {
            int cur = q.top();
            path[l++] = cur;
            q.pop();
            for (int i = 1; i <= n; i++) {
                if(G[cur][i]) {
                    digree[i]--;
                    if (!digree[i])
                        q.push(i);
                }
            }
        }
        for (int i = 0; i < l; i++) {
            printf("%d", path[i]);
            if (i != l-1) putchar(' ');
        }
        puts("");
    }
    return 0;
}

HDU 1811 Rank of Tetris

每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。接下来有M行，分别表示这些关系，问能否确定唯一排序关系。

如果一次入队入度为零的点大于1则说明拓扑排序序列不唯一
如果排序的总个数小于给定的个数,则说明存在回路

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 10000 + 5;

int fa[MAXN];
vector<int>G[MAXN];
int deg[MAXN];
int num;
bool cert;

void init(int n) {
    num = n; cert = true;
    for (int i = 0; i <= n; i++) {
        fa[i] = i;
        G[i].clear();
        deg[i] = 0;
    }
}

int findfa(int u) {
    if (fa[u] != u) fa[u] = findfa(fa[u]);
    return fa[u];
}

void unin(int u, int v) {
    int fau = findfa(u);
    int fav = findfa(v);
    if (fau == fav) return;
    if (fau < fav) {
        fa[fav] = fau;
    } else {
        fa[fau] = fav;
    }
    num--;
}

void toporder(int n) {
    queue<int>q;
    for (int i = 0; i < n; i++) {
        if (!deg[i] && fa[i] == i) q.push(i);
    }
    while (!q.empty()) {
        if (q.size() > 1) cert = false;
        int u = q.front(); q.pop();
        num--;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            if (!--deg[v]) {
                q.push(v);
            }
        }
    }
}


char r[MAXN][10];

int u[MAXN], v[MAXN];

int main() {
    //freopen("in.txt", "r", stdin);
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        init(n);
        for (int i = 0; i < m; i++) {
            scanf("%d%s%d", &u[i], r[i], &v[i]);
            if (r[i][0] == '=') {
                unin(u[i], v[i]);
            }
        }
        for (int i = 0; i < m; i++) {
            int uu = fa[u[i]], vv = fa[v[i]];
            if (r[i][0] == '<') {
                G[vv].push_back(uu);
                deg[uu]++;
            } else if (r[i][0] == '>') {
                G[uu].push_back(vv);
                deg[vv]++;
            }
        }
        toporder(n);
        if (num > 0) puts("CONFLICT");
        else if (!cert) puts("UNCERTAIN");
        else puts("OK");
    }
    return 0;
}