[POJ] 1094 Sorting It All Out.cpp

#include <cstdio>
#include <vector>
using namespace std;

vector<int> toNxt[30]; // toNxt[i]裡面存i這個點在哪些點前面
int deg[30];           // deg[i]表示在i前面有多少個點
vector<int> Ans;

void Initial(int N)
{
    Ans.clear();
    for (int i = 0; i < N; ++i) {
        toNxt[i].clear();
        deg[i] = -1;  // 用-1表示該點還沒出現過
    }
}
bool Trace(int a, int b) //確認a這個點是否在b這個點前面
{
    if (a == b) return true;
    for (int i = 0; i < toNxt[a].size(); ++i) {
        if (Trace(toNxt[a][i], b)) return true;
    }
    return false;
}
void topological_sort(int N)
{
    int Count = 0, a;
    for (int i = 0; i < N; ++i)
        if (deg[i] == 0){
            a = i;
            Count++;
        }
    if (Count != 1) return;  // 要確定這個lopological sort只有唯一解

    Ans.push_back(a);

    --deg[a];
    for (int i = 0; i < toNxt[a].size(); ++i)
        --deg[toNxt[a][i]];

    topological_sort(N);

    ++deg[a];
    for (int i = 0; i < toNxt[a].size(); ++i)
        ++deg[toNxt[a][i]];

}
int main()
{
    int N, M;
    char str[10];
    while (scanf("%d %d", &N, &M) && (N || M)) {
        Initial(N);

        int Inconsistency = 0;  //記錄關係式發生衝突的行數
        int hasAns = 0;         //記錄這Case是否有解

        for (int i = 0; i < M; ++i) {
            scanf("%s", str);
            int a = str[0]-'A';
            int b = str[2]-'A';

            //如果Inconsistency還沒記錄過且b在a的前面
            if (!Inconsistency && Trace(b, a))  Inconsistency = i + 1;
            else if(!Inconsistency){ // 如果沒有發生衝突
                toNxt[a].push_back(b);
                if (deg[a] == -1) deg[a] = 0;
                if (deg[b] == -1) deg[b] = 0;
                ++deg[b];

                Ans.clear();
                if (!hasAns) {
                    topological_sort(N);
                    if (Ans.size() == N) hasAns = i + 1;
                }
            }
        }
        if (hasAns) {
            printf("Sorted sequence determined after %d relations: ", hasAns);
            for (int i = 0; i < N; ++i)
                printf("%c", (char)Ans[i] + 'A');
            printf(".\n");
        }
        else {
            if (Inconsistency) printf("Inconsistency found after %d relations.\n", Inconsistency);
            else printf("Sorted sequence cannot be determined.\n");
        }
    }
}