POJ--1094--Sorting It All Out||NYOJ--349--Sorting It All Out（拓扑排序）

NYOJ的数据水一点，POJ过了是真的过了

/*
    拓扑排序模板题：
    每次输入都要判断有环与有序的情况，如果存在环路或者已经有序可以输出则跳过下面的输入
    判断有序，通过是否在一个以上的入度为0的点，存在则不能有序排列
    判断有环，如果拓扑排序完成存在一个有序的排列， 证明无环路 
        主要判断
            1.有序
            2.有环
        在无序的境况下，优先判断是否有环
        有序的情况下，优先判断是否能输出 
*/

#include <iostream> 
#include <vector>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 50;
vector<int> g[maxn];
int du[maxn], n, m, L[maxn];
int topsort() {
    memset(du, 0, sizeof(du));
    int flag = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<g[i].size(); j++) {
            du[g[i][j]]++; 
        }
    }
    int tot = 0;
    int ct = 0;
    queue<int> Q;
    for (int i=0; i<n; i++) {
        if (!du[i]) {
            Q.push(i);
            ct++;
        }
    }
    if (ct > 1) flag = -1;//无序
    while (!Q.empty()) {
        ct = 0;
        int x = Q.front();
        Q.pop();
        L[tot++] = x;
        for (int j=0; j<g[x].size(); j++) {
            int t = g[x][j];
            du[t]--;
            if (!du[t]) {
                Q.push(t);
                ct ++;
            }
        } 
        if (ct > 1) flag = -1;//无序 
    }
    if (flag == -1) {//无序情况下优先判断是否冲突
        if (tot != n) return 0;//有环 
        else return -1;
    }
    if (tot == n) return 1;
    return 0;//有环 
} 
int main() {
    
    while (cin>>n>>m && (m||n)) {
        int flag = 0;
        memset(g, 0, sizeof(g));
        for (int i=0; i<m; i++) {
            string str;
            cin>>str;
            if (flag) continue;
            int a = str[0] - 'A';
            int b = str[2] - 'A';
            g[a].push_back(b);
            int ans = topsort();
            if (ans == 1) {//有序 
                cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
                for (int i=0; i<n; i++) {
                    cout<<char(L[i]+'A');
                }
                cout<<"."<<endl;
                flag = 1;
            }
            if (ans == 0) {//环 ,冲突 
                cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
                flag = 1;
            }
        }
        if (!flag) {//无序 
            cout<<"Sorted sequence cannot be determined."<<endl;
        }
    }
    return 0;
}