poj1094 拓撲排序

http://poj.org/problem?id=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
ASample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
/**
poj 1094  拓撲排序
題目大意：
        對於N個大寫字母，給定它們的一些偏序關系，要求判斷出經過多少個偏序關系之後可以確定它們的排序或者存在沖突，
        或者所有的偏序關系用上之後依舊無法確定唯一的排序。        
解題思路：（來自網上）
        利用拓撲排序即可解決這個問題，但由於題目要求的是經過多少個關系之後就可以確定答案，因此每讀入一個關系，
        就要進行一次拓撲排序，如果某一次拓撲排序之後可以確定它們的唯一排序或者發現沖突存在，則後面的直接略過。
        若讀入所有關系之後依然無法確定唯一關系，同時也沒有沖突，則輸出不能確定唯一排序。若拓撲排序的過程中每次
        僅有一個點入度為0，則該排序是可以確定的排序，否則若多個點入度為0，則不知道哪個點先哪個點後。若拓撲排序
        進行到某一步之後無法再繼續，則說明存在回路，此時說明存在沖突。
*/

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=30;

int head[maxn],ip,indegree[maxn];
int n,m,seq[maxn];

struct note
{
    int v,next;
} edge[maxn*maxn];

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

void addedge(int u,int v)
{
    edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;
}

int topo()///拓撲，可做模板
{
    queueq;
    int indeg[maxn];
    for(int i=0; i