poj1094Sorting It All Out

主题链接：

题目：

Sorting It All Out

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 26897		Accepted: 9281

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

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.

Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

East Central North America 2001

这个题目对拓扑排序考虑的很细致。。

考虑了成环的情况。成环的情况也就是最后存在入度不为0的点。。

则计数后最后的num不等于n。。

这个题目还有就是这个题目不是对全部的信息进行综合推断，而是依据前面的假设可以得到已经成环了，或者可以得到n的大小顺序了，则后面的就不用推断了。。。所以用ok1，ok2两个变量进行控制。。

。

代码为：

#include<cstdio>
#include<stack>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=26+10;
int n,m;
int in[maxn],Copy[maxn],map[maxn][maxn],temp[maxn];
stack<int>S;
int topo()
{
    int flag=0,num=0;
    while(!S.empty())  S.pop();
    memcpy(Copy,in,sizeof(in));
    for(int i=0;i<n;i++)
    {
        if(Copy[i]==0)
            S.push(i);
    }
    while(!S.empty())
    {
        if(S.size()>1)
            flag=1;
        int Gery=S.top();
        S.pop();
        temp[num++]=Gery;
        for(int i=0;i<n;i++)
        {
            if(map[Gery][i])
            {
                if(--Copy[i]==0)
                   S.push(i);
            }
        }
    }
    if(num!=n)
        return 0;//成环。则已经能够确定关系了，能够标记。
    if(flag)
        return 1;//有多个入度为0的点，则还不确定。继续输入信息。添加条件，看能否够得到顺序。
    return 2;//顺序已经得到确定。能够标记。

}

int main()
{
    char str[maxn];
    int ok1,ok2,u,v,i,is_n;
    while(~scanf("%d%d",&n,&m),n,m)
    {
        is_n=0;
        memset(in,0,sizeof(in));
        memset(map,0,sizeof(map));
        ok1=ok2=0;
        for(i=1;i<=m;i++)
        {
            scanf("%s",str);
            if(!ok1&&!ok2)
            {
                u=str[0]-'A';
                v=str[2]-'A';
                if(map[u][v]==0)
                {
                    map[u][v]=1;
                    in[v]++;
                }
                int ans=topo();
                if(ans==0)
                {
                    is_n=i;
                    ok2=1;
                }
                else if(ans==2)
                {
                    is_n=i;
                    ok1=1;
                }
            }
        }
        if(ok1)
        {
            printf("Sorted sequence determined after %d relations: ",is_n);
            for(int i=0;i<n-1;i++)
                printf("%c",temp[i]+'A');
            printf("%c.
",temp[n-1]+'A');
        }
        if(ok2)
            printf("Inconsistency found after %d relations.
",is_n);
        if(ok1==0&&ok2==0)
          printf("Sorted sequence cannot be determined.
");
    }
    return 0;
}