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 = ;

vector<int> g[maxn];

int du[maxn], n, m, L[maxn];

int topsort() {

    memset(du, , sizeof(du));

    int flag = ;

    for (int i=; i<n; i++) {

        for (int j=; j<g[i].size(); j++) {

            du[g[i][j]]++;

        }

    }

    int tot = ;

    int ct = ;

    queue<int> Q;

    for (int i=; i<n; i++) {

        if (!du[i]) {

            Q.push(i);

            ct++;

        }

    }

    if (ct > ) flag = -;//无序

    while (!Q.empty()) {

        ct = ;

        int x = Q.front();

        Q.pop();

        L[tot++] = x;

        for (int j=; j<g[x].size(); j++) {

            int t = g[x][j];

            du[t]--;

            if (!du[t]) {

                Q.push(t);

                ct ++;

            }

        }

        if (ct > ) flag = -;//无序

    }

    if (flag == -) {//无序情况下优先判断是否冲突

        if (tot != n) return ;//有环

        else return -;

    }

    if (tot == n) return ;

    return ;//有环

}

int main() {

    while (cin>>n>>m && (m||n)) {

        int flag = ;

        memset(g, , sizeof(g));

        for (int i=; i<m; i++) {

            string str;

            cin>>str;

            if (flag) continue;

            int a = str[] - 'A';

            int b = str[] - 'A';

            g[a].push_back(b);

            int ans = topsort();

            if (ans == ) {//有序

                cout<<"Sorted sequence determined after "<<i+<<" relations: ";

                for (int i=; i<n; i++) {

                    cout<<char(L[i]+'A');

                }

                cout<<"."<<endl;

                flag = ;

            }

            if (ans == ) {//环 ,冲突

                cout<<"Inconsistency found after "<<i+<<" relations."<<endl;

                flag = ;

            }

        }

        if (!flag) {//无序

            cout<<"Sorted sequence cannot be determined."<<endl;

        }

    }

    return ;

}