poj1094(去环)(唯一确定)topu排序

Sorting It All Out

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 31940		Accepted: 11103

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.

---

一年前做过，当时没什么想法，只是照别人用floyd来判断环，现在做这题的想法是用Targan来判断强连通分量(环)，排除环以后，再拓扑来能否唯一确定判断先修关系
唯一的意思是a->b a->c c->d ,那么b和c的关系就不能判断了
所以每一次判断indegree时，只要判断in==0 是否唯一
但是本题有点恶心吧，题意要求输出能进行判断时的关系数量，表达不清楚额，，，所以每一步都要用拓扑来确定有没有单一关系，然后每一步都要进行Targan去掉环，感觉很麻烦的样子

后来看了别人的代码，发现直接用topu就能判断有没有环了，思路非常清晰
我们可以很容易发现，每一次进行topu判断时，只要不存在in == 0的结点，那么必然存在环，存在多个in==0的结点，那么说明此图不是唯一确定的

注意点：此题只要发现存在唯一确定，或者存在矛盾（也就是环），就会直接得到条件，换句话说，此题就是用最小的关系确定是否唯一确定，还是矛盾
特例是，前面唯一确定了，后面还是有矛盾，按此题的意思是不管后面的，因为前面先确定唯一了
非常经典的（排除环的）（唯一确定）的topu排序
RT

---

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int inf = 0x3f3f3f;
const int MAXN= 26;
const int MAXNN = 1e5+10;

int in[MAXN];
int tmp[MAXN];
int G[MAXN][MAXN];
int ans[MAXN];
int n,m,flag,signal;
int top;

void init(){
    flag= 1;
    signal = 0;
    memset(G,0,sizeof(G));
    memset(tmp,0,sizeof(tmp));
    memset(in,0,sizeof(in));
}

void tupoSort(){
    int sum,x;
    top=0;
    for(int i=0;i<n;i++){
        tmp[i] = in[i];
    }
    for(int i=0;i<n;i++){
        sum = 0;
        for(int j=0;j<n;j++){
            if(tmp[j]==0){
                sum++;
                x = j;
            }
        }
        if(sum==0){
            flag = -1;
            return;
        }

        if(sum>1){
            flag = 0;
        }

        tmp[x] = -1;
        ans[top++] = x;

        for(int j=0;j<n;j++){
            if(G[x][j]){
                tmp[j]--;
            }
        }
    }
    //flag = 2;
}


int main(){
    char ts[5];
    int a,b,w;
    while(scanf("%d%d",&n,&m),n){
        init();
        for(int i=0;i<m;i++){
            scanf("%s",ts);
            a = ts[0]-'A';
            b= ts[2]-'A';
            if(!G[a][b]){
                in[b]++;
                G[a][b] = 1;
            }
            else{
                continue;
            }
            if(signal)continue;
            flag = 1;
            tupoSort();
            if(flag==-1||flag==1){
                w = i+1;
                signal = 1;
            }
        }

        if(flag==0)
            printf("Sorted sequence cannot be determined.
");
        else if(flag==-1)
            printf("Inconsistency found after %d relations.
",w);
        else {
            printf("Sorted sequence determined after %d relations: ",w);
                for(int i=0;i<top;i++){
                    printf("%c",ans[i]+'A');
                }
                cout<<"."<<endl;
        }
    }
}