POJ-1094 拓扑排序

题意：从'A'到'A'+n的n个字母，给出m个大小关系，求是否有特定的拓扑排序。

总结：题目有点坑人。 1、不会有超出'A'+n范围的字母。 2、如果在输入第k个字母时，已经可以判断出有特定的排序或者判断出矛盾(即有环)，就不用管后面的了。 3、判断是否有特定的排序，故有多种可能的应算作无序；而且如果即是无序又是矛盾的，应算作矛盾。

// POJ-1094 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<bitset>
#include<vector>
#include<set>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define F(i,a,b)  for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 30;

int n, m, c;
int G[N][N], indegree[N], List[N];

int Toposort(int e)
{
    int in[N], Q[N], top=0, flag=1;
    mes(List, 0);
    c=0;
    FF(i,1,n) {
        in[i]=indegree[i];
        if(in[i]==0) {
            Q[top++]=i, List[c++]=i, in[i]=-1;
        }
    }
    if(top>1) flag=0;
    while(top!=0) {
        int u=Q[--top];
        FF(i,1,n) if(G[u][i]) {
            in[i]--, e--;
            if(in[i]==0) {
                Q[top++]=i, List[c++]=i, in[i]=-1;
            }
            if(top>1) flag=0;
        }
    }
    if(e!=0) return -1;
    return flag;
}
int main()
{
    while(~scanf("%d%d", &n, &m) &&n&&m) {
        mes(G, 0);  mes(indegree, 0);
        int flag=0, ans=0;
        FF(i,1,m) {
            char str[10];
            scanf("%*c%s", str);
            if(flag==1) continue;
            int a=str[0]-'A'+1, b=str[2]-'A'+1;
            G[a][b]=1, indegree[b]++;
            int topo=Toposort(i);
            if(topo!=0) ans=i, flag=1;
            if(topo==1) {
                printf("Sorted sequence determined after %d relations: ", ans);
                F(i,0,c) printf("%c", 'A'+List[i]-1);
                puts(".");
            }
            else if(topo==-1) {
                printf("Inconsistency found after %d relations.
", ans);
            }
        }
        if(flag==0)  printf("Sorted sequence cannot be determined.
");
    }

    return 0;
}

View Code

下面是大牛博客对拓扑排序Kahn算法的总结：

不难看出该算法的实现十分直观，关键在于需要维护一个入度为0的顶点的集合：

每次从该集合中取出(没有特殊的取出规则，随机取出也行，使用队列/栈也行，下同)一个顶点，将该顶点放入保存结果的List中。

紧接着循环遍历由该顶点引出的所有边，从图中移除这条边，同时获取该边的另外一个顶点，如果该顶点的入度在减去本条边之后为0，那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点…………

当集合为空之后，检查图中是否还存在任何边，如果存在的话，说明图中至少存在一条环路。不存在的话则返回结果List，此List中的顺序就是对图进行拓扑排序的结果。