POJ-1094-Sorting It All Out

链接：https://vjudge.net/problem/POJ-1094#author=TIMEpings

题意：

用小于号"<"来定义两元素之间的关系，并于一个没有重复元素的有序上升序列 从小到大地排列这些元素。
比如说，序列A,B,C,D意味着A<B;B<C;C<D。
在这个问题里，我们会给你一组形如"A<B"的关系，询问你有序序列的合法性或其本身。

思路：

要输出成功和失败是第几次。

所以每输入一次，进行一次拓扑排序。

拓扑序内记录情况，记住，不能完全确定排名时，不能直接返回，因为可能存在环还没有判断到。

因为这个wa了1个小时。。。

代码：

#include <iostream>
#include <memory.h>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <queue>
#include <string>
#include <stack>
#include <iterator>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

using namespace std;
typedef long long LL;
const int MAXN = 30;
int in[MAXN];
int tmp[MAXN];
vector<int> G[MAXN];
vector<int> res;
int n, m;

void Init()
{
    for (int i = 1;i <= n;i++)
        G[i].clear();
    memset(in, 0, sizeof(in));
}

int Tupo()
{
    for (int i = 1;i <= n;i++)
        tmp[i] = in[i];
    res.clear();
    queue<int> que;
    for (int i = 1;i <= n;i++)
        if (tmp[i] == 0)
            que.push(i);
    int flag = 0;
    while (!que.empty())
    {
        if (que.size() > 1)
            flag = 1;
        int u = que.front();
        que.pop();
        res.push_back(u);
        for (int i = 0;i < G[u].size();i++)
        {
            if (--tmp[G[u][i]] == 0)
                que.push(G[u][i]);
        }
    }
    if (res.size() < n)
        return -1;
    if (flag)
        return 0;
    return 1;
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0)
            break;
        Init();
        char l, r;
        int flag = 0;
        for (int i = 1;i <= m;i++)
        {
            scanf(" %c<%c", &l, &r);
            //cout << l << ' ' << r << endl;
            int u = l-'A'+1;
            int v = r-'A'+1;
            //cout << u << ' ' << v << endl;
            if (flag != 0)
                continue;
            G[u].push_back(v);
            ++in[v];
            flag = Tupo();
            if (flag == 1)
            {
                printf("Sorted sequence determined after %d relations: ", i);
                for (int j = 0;j < res.size();j++)
                    printf("%c", (char)(res[j]+'A'-1));
                printf(".
");
            }
            if (flag == -1)
                printf("Inconsistency found after %d relations.
", i);
        }
        if (flag == 0)
            printf("Sorted sequence cannot be determined.
");
    }

    return 0;
}