一.题目链接：

POJ-1094

二.题目大意：

给出 n，m.

字母由 A 到 A + n.

给出 m 个关系，形式如：A<B.

输入结束后

若字母顺序已确定，则输出 "Sorted sequence determined after 最少步数 relations: 字母顺序."

若有矛盾，则输出 "Inconsistency found after 最小步数 relations."

否则输出 "Sorted sequence cannot be determined."

三.分析：

①链式向前星存图 

太水了，不解释

②拓扑排序

首先来思考一个问题 —— 什么时候才会矛盾、顺序确定、无法确定呢？

若出现了矛盾，即出现了环，此时 (入度为 0 和 入度可变为 0) 的结点数目 一定小于 n.

若顺序确定，即构成了欧拉回路，此时在任意时刻都只有一个入度为 0 的结点，

并且根据这个结点可以搜到所有剩余结点.

否则无法确定.

这个题的题意貌似有些问题，只要在第 i 步出现矛盾 或 顺序确定，不管后面如何，都按照最前状态输出.

可能是本菜鸡又菜了，连题目都没读懂.

例如

2 2

A<B

B<A

在第一步已经确定了字母顺序，所以输出 "Sorted sequence determined after 1 relations: AB."

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;

const int M = 30;
int cnt;
int seq[M];
int head[M];
int indegree1[M];
struct node
{
    int to;
    int next;
} edge[M * M];

void init(int n)
{
    cnt = 1;
    for(int i = 1; i <= n; ++i)
    {
        indegree1[i] = 0;
        head[i] = -1;
    }
}

void add(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    indegree1[v]++;
}

int toposort(int n)
{
    int q[M];
    int fron = 0;
    int rear = 0;
    int indegree2[M];
    for(int i = 1; i <= n; ++i)
    {
        indegree2[i] = indegree1[i];
        if(!indegree2[i])
            q[rear++] = i;
    }
    int len = 0;
    bool flag = 0;
    while(fron != rear)
    {
        if(fron + 1 < rear)
            flag = 1;
        int tmp = q[fron++];
        seq[len++] = tmp;
        int t = head[tmp];
        while(~t)
        {
            indegree2[edge[t].to]--;
            if(!indegree2[edge[t].to])
                q[rear++] = edge[t].to;
            t = edge[t].next;
        }
    }
    if(len < n)
        return -1;
    if(flag)
        return 0;
    return 1;
}

int main()
{
    int n, m;
    while(~scanf("%d %d", &n, &m))
    {
        if(n + m == 0)
            break;
        init(n);
        int success, error;
        success = error = -1;
        for(int i = 1; i <= m; ++i)
        {
            getchar();
            char s[5];
            scanf("%s", s);
            if(~error || ~success)
                continue;
            int u = s[0] - 'A' + 1;
            int v = s[2] - 'A' + 1;
            add(u, v);
            int ans = toposort(n);
            if(ans == 1)
                success = i;
            if(ans == -1)
                error = i;
        }
        if(~error)
            printf("Inconsistency found after %d relations.\n", error);
        else if(~success)
        {
            printf("Sorted sequence determined after %d relations: ", success);
            for(int i = 0; i < n; ++i)
                putchar(seq[i] + 'A' - 1);
            printf(".\n");
        }
        else
            printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}