poj1094 拓扑排序

/*
给定一组偏序关系，问最少第几步能确定次序
如果出现环，问第几步出现环
因为要求第几步确定次序或者第几步出现环，所以每次读入一个偏序关系就进行一次拓扑排序 
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 50;
int in[N]; //入度
bool Map[N][N]; //临接矩阵此题可以随便用 
char out[N]; //拓扑排序输出数组

int topsort( int n ) {
    priority_queue<int,vector<int>,greater<int> > q;  //优先队列忠实粉丝 
    int flag = 0,k;
    int zeroflag = 0;
    int num = 0,temp[N];
    memcpy(temp,in,sizeof(in));//拷贝
    for( int i = 0; i < n; i++ ) {
        if( !in[i] ) q.push(i);
    }
    while( !q.empty() ) {
        if( q.size() > 1 )
            zeroflag = 1;//要注意在while里面判断 因为此过程中也可能出现入度0不止一个的情况
        k = q.top();
        q.pop();
        num++;
        out[num] = k + 'A'; //num计数 以存到out里面
        for(int i = 0; i < n; i++ )
            if(Map[k][i]==1 && --temp[i] == 0)
                q.push(i);
    }
    if( num != n ) return 1;
    if( zeroflag == 1 ) return 0;//多个点入度为零
    return -1; 
} 
int main(){
    int n,m,k;
    int step; //记录操作数
    int circleflag,orderflag;
    char s[6];
    while( scanf("%d%d", &n, &m) != EOF && n ){
        circleflag=0;orderflag=0;
        memset(Map,0,sizeof(Map));
        memset(in,0,sizeof(in));
        for( int i = 1; i <= m; i++ ){
            scanf("%s", s);
            if( circleflag == 0 && orderflag == 0 ){ //已经判出了 就不读了
                if(Map[s[2]-'A'][s[0]-'A'] == 1){
                    circleflag=1; //有环了
                    printf("Inconsistency found after %d relations.
", i);
                    continue ;
                }
                if(Map[s[0]-'A'][s[2]-'A'] == 0){
                    Map[s[0]-'A'][s[2]-'A'] = 1;
                    in[s[2]-'A']++;
                }
                k = topsort(n);
                if( k == 1 ){
                    circleflag=1;
                    printf("Inconsistency found after %d relations.
", i);
                }
                else if( k == -1 ){
                    orderflag=1;
                    step=i; //记录位置
                }
            }
        }
        if(circleflag == 0 && orderflag == 0)
            printf("Sorted sequence cannot be determined.
");
        else if(orderflag == 1){
            printf("Sorted sequence determined after %d relations: ", step);
            for(int i=1; i<=n; i++)
                printf("%c", out[i]);
            printf(".
");
        }
    }
    return 0;
}