poj1094 Sorting It All Out 拓扑排序

http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
这个方法很简单，思路是这样的，对于每次输入一个关系后，我们就对输入进行一次拓扑排序，拓扑排序的结果有三种情况。
结果确定的两种情况：
第一种，如果排序后，序列中的节点数目<n,说明出现了环，因此应该直接输出，一旦结果确定，以后的输入就不用判断了。
第二种，如果排序后，节点数目刚好等于n，并且序列里相邻的节点已经明确出现了<,关系，说明大小关系已经确定了
还有一种，只能说明到目前为止知道的信息不足以判断，还需要继续看以后的输入才行
第三种情况，即排序后，节点数目刚好等于n，但是序列里相邻的节点还未明确出现<关系

代码如下：
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 26
#define debug
#undef debug
using namespace std;
bool top_sort(int G[MAX_N][MAX_N],int n ,int relation_no){
    bool is_add[MAX_N];
    int temp_g[MAX_N][MAX_N];
    vector <int> sorted_res;
    memset(is_add,false,sizeof(is_add));
    for(int i = 0 ; i < MAX_N ; i++){
        for(int j = 0 ; j < MAX_N ; j++)
                temp_g[i][j] = G[i][j];
    }

    #ifdef debug
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++)
                printf("%d ",temp_g[i][j]);
        printf("\n");
    }

    #endif

    while(true){
        int next_add = -1;
        for(int i = 0 ; i < n ; i++){
                if(is_add[i]) continue;
                bool can_be_add = true;
                for(int j = 0 ; j < n ; j++){
                    can_be_add = can_be_add && (temp_g[j][i] == 0);           
                }
                if(can_be_add){
                    is_add[i] = true;           
                    next_add = i;  
                    #ifdef debug
                    printf("%d ",i);
                    #endif     
                    break;  
                }              

        }
        if(next_add < 0) break;
        sorted_res.push_back(next_add);
        for(int j = 0 ; j < n ; j++){
                temp_g[next_add][j] = 0;
        }

    }
    if(sorted_res.size() < n){
        printf("Inconsistency found after %d relations.\n",relation_no);
        return true;
    }
    else{
        bool is_determined = true;
        for(int i = 1 ; i < sorted_res.size() ; i++){
                is_determined = is_determined&&G[sorted_res[i-1]][sorted_res[i]];//attention please we should use G instead of temp_g
        }
        if(is_determined){
                printf("Sorted sequence determined after %d relations: ",relation_no);
                for(int i = 0 ; i < sorted_res.size() ; i++){
                       printf("%c",sorted_res[i]+’A’);        
                }
               
                printf(".\n");
                return true;
        }
        else{
                return false;
        }
    }

}
int main()
{  
    int n,m;
    while(scanf("%d%d",&n,&m) && !(n==0 && m==0)){
        char temp[MAX_N];
        int g[MAX_N][MAX_N];
        for(int i = 0 ; i < MAX_N ; i++){
        for(int j = 0 ; j < MAX_N ; j++)
                g[i][j] = 0;
        }
        bool is_determined = false;
        for(int i = 0 ; i < m ; i++){
                scanf("%s",temp);
                g[temp[0]-‘A’][temp[2]-‘A’] = 1;
                if(!is_determined){
                    is_determined = top_sort(g,n,i+1);           
                }
               
        }
        if(!is_determined)
                printf("Sorted sequence cannot be determined.\n");
    }
 
  return 0;

}