#include<cstdio>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cassert>
#include<vector>
#include<deque>
#include<list>
#include<set>
#include<map>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

const int MAXN = 30 + 10;
const int INF_MAX = 1 << 28;
const double INF_MIN = 1e-8;

int n, m;
int edge[MAXN][MAXN];

bool input() {
    cin >> n >> m;
    if (n == 0 && m == 0) {
        return false;
    }
    memset(edge, 0, sizeof(edge));
    return true;
}

void kahn(int &idx, int *ans, bool &hasHuan, bool &isWeiYi) {
    int *degree = new int[n];
    memset(degree, 0, n * sizeof(n));
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            degree[j] += edge[i][j];
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (degree[i] == 0) {
            q.push(i);
        }
    }

    isWeiYi = true;
    idx = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans[idx++] = u;
        if ((int)q.size() != 0) {
            isWeiYi = false;
        }

        for (int j = 0; j < n; j++) {
            if (edge[u][j] == 1) {
                degree[j]--;
                if (degree[j] == 0) {
                    q.push(j);
                }
            }
        }
    }

    hasHuan = idx < n;
}

void solve() {
    int idx;
    int *ans = new int[n];
    bool isEnd = false;

    for (int i = 1; i <= m; i++) {
        char c1, tmp, c2;
        cin >> c1 >> tmp >> c2;
        edge[c1 - 'A'][c2 - 'A'] = 1;

        if (isEnd) {
            continue;
        }

        bool hasHuan;
        bool isWeiYi;
        kahn(idx, ans, hasHuan, isWeiYi);
        if (hasHuan) {
            cout << "Inconsistency found after ";
            cout << i << " relations.\n";
            isEnd = true;
            continue;
        }
        if (!hasHuan && isWeiYi) {
            cout << "Sorted sequence determined after ";
            cout << i;
            cout << " relations: ";
            for (int i = 0; i < idx; i++) {
                cout << (char)(ans[i] + 'A');
            }
            cout << ".\n";
            isEnd = true;
            continue;
        }
    }
    if (!isEnd) {
        cout << "Sorted sequence cannot be determined.\n";
    }
}

int main()
{
    //freopen("input.cpp", "r", stdin);///
    //freopen("output.cpp", "w", stdout);///

    while (input()) {
        solve();
    }

   	return 0;
}

• Re:kahn写的，需要判断是否有环和是否唯一 (6) jdq8576 2017-12-07 20:54:36