题目链接：

http://poj.org/problem?id=1094

题意：

给定前n个字母的大小关系，问你是否

1. 根据前xxx个关系得到上升序列
2. 所有关系都无法确定唯一的一个序列
3. 第xxx个关系导致出现环

分析：

此题坑略多。。。。

1. m大小没给！！这个很无语啊。。。数组开大点马上AC了。。。
2. 无法确定序列必须最后判断。
3. 一旦可以判断出上升序列，就不用管后面是否出现闭环了~~

where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.

代码：

#include<iostream>

#include<queue>

#include<stack>

#include<cstring>

#include<cstdio>

using namespace std;

const int maxn = 1005;

vector<int>G[maxn];

int in[maxn];

int ef[maxn], et[maxn];

int n, m;

queue<int>s;

int vis[maxn];

int judge(int num)

{

     while(!s.empty()) s.pop();

     int cnt = 0;

     memset(in, 0,sizeof(in));

     memset(vis, 0, sizeof(vis));

     for(int i = 0; i < maxn; i++)

        G[i].clear();

    for(int i = 0; i <= num; i++){

        G[ef[i]].push_back(et[i]);

        in[et[i]]++;

        if(!vis[et[i]]) cnt++;

        if(!vis[ef[i]]) cnt++;

        vis[et[i]] = vis[ef[i]] = 1;

    }

    queue<int>q;

    for(int j =0; j < n; j++){

        if(vis[j] && !in[j])

                q.push(j);

    }

    int flg = 0;

    while(!q.empty()){

        int u = q.front();q.pop();

        if(q.size()) flg = 1;

        s.push(u);

        for(int k = 0; k < G[u].size(); k++){

            int v = G[u][k];

            in[v]--;

            if(!in[v]) q.push(v);

        }

    }

    //cout<<s.size()<<' '<<cnt<<endl;

    if(s.size() == n && !flg) return 3;

    return s.size() == cnt;

}

int main (void)

{

   while(scanf("%d%d",&n, &m) && n+m != 0){

    for(int i = 0; i <maxn; i++)

        G[i].clear();

    getchar();

    char a, b;

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

        scanf("%c%*c%c", &a, &b);

        getchar();

        ef[i] = a - 'A';

        et[i] = b - 'A';

    }

    int i;

    int flag = 0;

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

        int t = judge(i);

        if(t == 3){flag = 1;break;}

        else if(t == 0){break;}

    }

    if(flag){

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

        while(!s.empty()){cout<<(char)(s.front()+'A');s.pop();}

        cout<<'.'<<endl;

    } else if(i == m)  cout<<"Sorted sequence cannot be determined."<<endl;

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

   }

    return 0;

}

感觉这题的代码写的好挫。。。。