poj 1094 拓扑排序

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.
题意：

这道题有隐含这一信息，每输入一对关系，如果判定有结果，则可以忽略后面输入数据，即使后面输入数据能改变结果，也不用管。所以应该每输入一个关系就去更新当前的图，然后进行一趟拓扑排序。一旦产生结果，再对后面的数据处理下，就可以输出结果。

一、当输入的字母全部都在前n个大写字母范围内时：

（1）最终的图可以排序：

在输入结束前如果能得到最终的图（就是用这n个字母作为顶点，一个都不能少）；而且最终得到的图无环；只有唯一一个无前驱（即入度为0）的结点，但允许其子图有多个无前驱的结点。

在这步输出排序后，不再对后续输入进行操作

（2）输出矛盾

在输入结束前如果最终图的子图有环

在这步输出矛盾后，不再对后续输入进行操作

（3）输出无法确认排序

这种情况必须全部关系输入后才能确定，其中又有2种可能

①最终图的字母一个不缺，但是有多个无前驱结点

②输入结束了，但最终的图仍然字母不全，与无前驱结点的多少无关

二、当输入的字母含有非前n个大写字母的字母时（超出界限）：

（1）输出矛盾

输入过程中检查输入的字母（结点），若前n个大写字母全部出现，则在最后一个大写字母出现的那一步输出矛盾

（2）输出无法确认排序

最后一步输入后，前n个大写字母仍然未全部出现，则输出无法确认排序

PS：在使用“无前驱结点”算法时必须要注意，在“矛盾优先”的规律下，必须考虑一种特殊情况，就是多个无前驱结点与环共存时的情况，即输入过程中子图都是有多个无前驱结点，最后一步输入后出现了环，根据算法的特征，很容易输出“不能确认排序”，这是错的，必须适当修改算法，输出“矛盾”。

#include<stdio.h>
#include<string.h>
int map[27][27],indegree[27],q[27];
int TopoSort(int n) //拓扑排序
{
    int c=0,temp[27],loc,m,flag=1,i,j;  ////flag=1:有序 flag=-1:不确定
    for(i=1;i<=n;i++)
        temp[i]=indegree[i];
    for(i=1;i<=n;i++)
    {
        m=0;
        for(j=1;j<=n;j++)
            if(temp[j]==0) { m++; loc=j; }  //查找入度为零的顶点个数
        if(m==0) return 0;  //有环
        if(m>1) flag=-1;  // 无序
        q[c++]=loc;   //入度为零的点入队
        temp[loc]=-1;
        for(j=1;j<=n;j++)
            if(map[loc][j]==1) temp[j]--;
    }
    return flag;
}

int main()
{
    int m,n,i,sign;  //当sign=1时，已得出结果
    char str[5];
    while(scanf("%d%d",&n,&m))
    {
        if(m==0&&n==0) break;
        memset(map,0,sizeof(map));
        memset(indegree,0,sizeof(indegree));
        sign=0;
        for(i=1;i<=m;i++)
        {
            scanf("%s",str);
            if(sign) continue; //一旦得出结果，对后续的输入不做处理
            int x=str[0]-'A'+1;
            int y=str[2]-'A'+1;
            map[x][y]=1;
            indegree[y]++;
            int s=TopoSort(n);
            if(s==0) //有环
            {
                printf("Inconsistency found after %d relations.
",i);
                sign=1;
            }
            if(s==1) //有序
            {
                printf("Sorted sequence determined after %d relations: ",i);
                for(int j=0;j<n;j++)
                    printf("%c",q[j]+'A'-1);
                printf(".
");
                sign=1;
            }
        }
        if(!sign) //不确定
            printf("Sorted sequence cannot be determined.
");
    }
    return 0;