POJ 1094-Sorting It All Out(元素大小关系-拓扑排序)

系统管理员 2022-09-24 11:29 125阅读 0赞

Sorting It All Out

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;32635</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;11345</td> 
  </tr> 
 </tbody> 
</table>

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][]

## 题目意思： ##

由一些不同元素组成的升序序列可以使用若干个 小于号将所有的元素按从小到大的顺序排列起来的序列。

例如，排序后为ABCD，这说明A<B,B<C,C<D.

给定一组形如A<B的表达式，是判断是否存在一个有序序列。

## 解题思路： ##

拓扑排序。

先建图用邻接矩阵存边，再用一个数组记录下所有的入边度数。

分三种情况讨论：

①图中存在环；

② 图中不存在环，拓扑排序后元素个数小于N，说明无法确定全部元素的大小关系；

③ 图中不存在环， 拓扑排序后元素个数等于N，直接输出拓扑序列即为正确的大小关系。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<cstdlib>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define MAXN 30//开太大会超内存
    int n,m;
    char top[MAXN];
    int in[MAXN],temp[MAXN],e[MAXN][MAXN];
    bool vis[MAXN];
    
    int topsort()
    {
        int i,j,k,cnt,cto=0;
        int flag=1;
        memcpy(temp,in,sizeof(in));
        for(k=0; k<n; ++k)
        {
            cnt=0;
            for(i=0; i<n; ++i)
                if(temp[i]==0)
                {
                    j=i;
                    ++cnt;//入度为0的点的个数
                }
            if(cnt==0) return 0;//有环
            if(cnt>1) flag=-1;//无序
            for(i=0; i<n; ++i)
                if(e[j][i]==1)//有边
                    --temp[i];//删去当前度为0的点的出边
            top[cto++]=j+'A';//拓扑序列
            temp[j]=-1;
        }
        return flag;
    }
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/x/read.txt","r",stdin);
        freopen("G:/x/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        while(cin>>n>>m&&n!=0&&m!=0)
        {
            memset(vis,false,sizeof(vis));
            memset(in,0,sizeof(in));
            memset(e,0,sizeof(e));
            memset(top,0,sizeof(top));//注意这些数组一定要清除干净
            char a,b,c;
            int t=0;
            bool istop=false;//是否判断完毕
            for(int i=0; i<m; ++i)
            {
                cin>>a>>c>>b;
                if(istop) continue;//判断完之后只读入不再处理
                e[int(a)-'A'][int(b)-'A']=1;//存边
                ++in[int(b)-'A'];//入边
                t=topsort();//拓扑排序
                if(t==0)
                {
                    cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
                    istop=true;
                }
                else if(t==1)
                {
                    cout<<"Sorted sequence determined after "<<i+1<<" relations: "<<top<<"."<<endl;
                    istop=true;
                }
            }
            if(!istop) cout<<"Sorted sequence cannot be determined."<<endl;
        }
        return 0;
    }
    /**
    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
    **/

## 分享几组测试数据： ##

4 6
    D<B
    D<A
    D<C
    C<A
    C<B
    A<B
    10 40
    C<I
    E<G
    A<J
    F<B
    D<E
    F<D
    C<B
    E<H
    G<I
    D<B
    C<H
    A<B
    J<I
    D<G
    A<E
    C<G
    E<B
    H<G
    C<A
    F<J
    B<G
    D<J
    E<J
    D<H
    C<F
    B<J
    G<J
    B<H
    D<A
    F<I
    A<H
    C<E
    F<H
    A<G
    B<I
    F<A
    H<J
    F<G
    F<E
    C<J
    15 60
    B<M
    M<H
    N<G
    N<E
    I<D
    B<D
    A<J
    O<D
    D<J
    F<E
    I<L
    F<B
    I<C
    C<E
    I<K
    I<J
    A<E
    B<L
    G<J
    A<G
    N<H
    H<J
    K<N
    K<E
    F<J
    C<D
    K<M
    G<L
    F<H
    M<L
    A<K
    B<K
    E<L
    B<H
    F<D
    M<E
    M<G
    N<L
    O<J
    D<H
    B<O
    B<C
    A<L
    I<B
    F<L
    C<L
    A<C
    N<O
    A<B
    F<C
    K<J
    C<G
    O<E
    I<O
    D<E
    I<N
    F<N
    M<J
    H<L
    N<D
    15 60
    B<M
    M<H
    N<G
    N<E
    I<D
    B<D
    A<J
    O<D
    D<J
    F<E
    I<L
    F<B
    I<C
    C<E
    I<K
    I<J
    A<E
    B<L
    G<J
    A<G
    N<H
    H<J
    K<N
    K<E
    F<J
    C<D
    K<M
    G<L
    F<H
    M<L
    A<K
    B<K
    E<L
    B<H
    F<D
    M<E
    M<G
    N<L
    O<J
    D<H
    O<B
    B<C
    A<L
    I<B
    F<L
    C<L
    A<C
    N<O
    A<B
    F<C
    K<J
    C<G
    O<E
    I<O
    D<E
    I<N
    F<N
    M<J
    H<L
    N<D
    26 325
    J<I
    L<P
    K<S
    M<X
    K<E
    H<W
    Z<S
    G<R
    F<R
    A<Y
    V<D
    P<X
    P<W
    M<S
    R<A
    G<V
    C<H
    O<R
    A<S
    N<C
    V<Y
    A<I
    F<Z
    V<Q
    V<R
    H<I
    Q<T
    M<Q
    F<A
    J<X
    M<D
    C<Q
    D<E
    V<F
    B<T
    X<U
    D<U
    G<Y
    V<B
    B<J
    N<U
    K<Z
    P<S
    E<U
    O<Y
    M<Z
    C<I
    F<S
    G<P
    O<J
    C<S
    W<U
    Z<Y
    D<L
    H<T
    B<Q
    X<W
    D<I
    K<B
    R<L
    L<X
    S<Q
    K<F
    B<R
    C<L
    O<B
    Y<S
    F<Y
    X<T
    S<U
    C<W
    O<P
    B<Z
    V<U
    C<X
    H<U
    O<U
    V<W
    D<A
    O<X
    G<D
    P<A
    D<X
    E<T
    S<T
    C<T
    H<O
    J<Q
    K<H
    Z<Q
    Z<W
    I<T
    J<A
    Z<E
    F<L
    Q<U
    J<S
    N<H
    J<E
    B<D
    M<I
    K<R
    Z<X
    B<Y
    P<Y
    R<E
    F<O
    R<P
    C<A
    D<Y
    D<Z
    B<X
    M<A
    I<Q
    K<J
    J<Z
    O<W
    H<R
    L<Q
    M<F
    W<T
    F<X
    F<E
    A<W
    N<J
    K<O
    H<S
    F<B
    V<K
    O<A
    R<U
    M<W
    M<K
    E<W
    C<D
    N<S
    S<E
    Y<I
    G<N
    F<P
    N<P
    G<W
    M<B
    J<W
    M<J
    X<Q
    Y<Q
    Y<E
    P<Q
    S<W
    J<T
    Z<U
    I<U
    M<Y
    F<Q
    V<Z
    J<D
    C<J
    K<Q
    A<Q
    M<U
    S<I
    C<O
    Z<I
    H<B
    G<A
    P<T
    G<F
    X<E
    B<U
    O<I
    C<F
    O<L
    N<V
    F<T
    J<L
    D<T
    R<S
    N<E
    L<T
    M<N
    O<D
    K<X
    V<L
    G<B
    O<E
    R<Y
    G<I
    O<Z
    G<U
    Z<L
    R<T
    N<Q
    C<Y
    M<C
    K<I
    O<S
    H<E
    R<X
    R<W
    H<J
    G<K
    E<I
    C<U
    H<A
    L<E
    N<F
    V<X
    N<W
    M<P
    H<F
    F<I
    R<Z
    K<T
    N<Y
    D<W
    G<J
    N<I
    G<S
    M<L
    N<X
    F<U
    L<Y
    G<H
    G<E
    D<S
    C<B
    V<P
    V<A
    V<I
    G<L
    B<L
    W<Q
    T<U
    N<D
    V<T
    P<I
    B<I
    N<Z
    P<E
    K<C
    E<Q
    K<D
    N<K
    B<E
    V<H
    G<T
    B<P
    V<J
    D<Q
    L<S
    M<T
    M<R
    K<A
    P<U
    N<A
    Z<A
    L<I
    V<E
    H<L
    K<Y
    A<T
    J<P
    C<R
    K<W
    M<H
    B<W
    N<T
    C<P
    G<Z
    R<D
    H<P
    Z<T
    X<S
    H<D
    G<O
    N<R
    L<W
    F<D
    H<Q
    R<I
    V<C
    V<O
    N<O
    L<U
    Z<P
    N<L
    C<E
    O<Q
    H<X
    F<J
    G<C
    D<P
    A<U
    A<E
    M<E
    J<Y
    I<W
    G<X
    L<A
    B<S
    N<B
    H<Y
    C<Z
    B<A
    Y<U
    X<A
    K<L
    Y<T
    R<J
    H<Z
    R<Q
    Y<W
    V<S
    X<Y
    G<Q
    K<U
    G<M
    M<V
    X<I
    J<U
    K<P
    M<O
    F<W
    O<T
    26 26
    A<B
    B<C
    C<D
    D<E
    E<F
    F<G
    G<H
    H<I
    I<J
    J<K
    K<L
    L<M
    M<N
    N<O
    O<P
    P<Q
    Q<R
    R<S
    S<T
    T<U
    U<V
    V<W
    W<X
    X<Y
    Y<Z
    Z<A
    5 10
    D<E
    A<D
    B<D
    B<C
    C<E
    D<C
    B<A
    A<C
    A<E
    B<E
    20 158
    I<L
    F<R
    I<C
    N<B
    C<K
    R<O
    E<D
    D<K
    F<S
    A<C
    J<E
    H<A
    N<D
    N<T
    H<I
    A<T
    M<S
    T<O
    P<Q
    G<J
    B<L
    N<I
    A<R
    T<S
    M<J
    B<J
    G<P
    N<E
    B<D
    N<F
    K<Q
    B<E
    E<O
    M<P
    M<F
    A<F
    H<S
    G<D
    P<J
    A<Q
    T<F
    G<F
    T<R
    L<Q
    A<J
    G<I
    H<O
    C<D
    P<L
    H<T
    T<E
    D<Q
    J<O
    A<M
    F<E
    E<K
    E<Q
    P<T
    C<E
    M<B
    T<J
    G<E
    N<K
    I<P
    M<Q
    H<M
    G<L
    I<J
    P<S
    A<K
    F<L
    T<L
    G<T
    I<Q
    B<O
    H<N
    M<G
    J<R
    C<B
    N<O
    T<D
    A<D
    L<S
    I<K
    R<Q
    M<E
    B<R
    O<Q
    R<D
    I<T
    T<Q
    I<D
    O<D
    N<Q
    A<S
    M<K
    H<G
    G<C
    H<E
    B<Q
    H<B
    G<S
    I<S
    I<R
    J<Q
    A<L
    F<Q
    J<D
    C<J
    H<L
    A<P
    F<K
    L<E
    I<O
    N<P
    E<S
    A<I
    C<R
    N<L
    T<B
    H<K
    R<K
    A<G
    C<Q
    J<K
    C<T
    P<B
    H<F
    O<K
    R<L
    O<S
    G<O
    M<I
    K<S
    F<O
    G<R
    B<S
    P<E
    T<K
    G<B
    A<O
    I<B
    P<C
    N<M
    J<F
    H<R
    F<D
    P<D
    H<P
    G<Q
    P<R
    L<K
    H<Q
    S<Q
    H<D
    C<O
    N<S
    N<A
    10 40
    E<J
    C<A
    G<J
    C<H
    G<I
    A<I
    D<I
    D<A
    G<E
    F<I
    A<J
    D<H
    E<B
    A<B
    D<E
    E<I
    D<C
    C<G
    F<A
    F<H
    D<B
    I<J
    I<B
    F<C
    J<B
    D<F
    G<H
    A<H
    I<H
    A<E
    E<H
    F<J
    H<B
    G<A
    G<F
    D<G
    F<E
    F<B
    C<B
    C<I
    20 70
    K<Q
    P<L
    I<C
    O<L
    I<M
    B<Q
    G<R
    J<E
    O<E
    J<C
    J<N
    H<T
    A<D
    G<B
    I<O
    S<K
    H<F
    J<L
    Q<C
    G<K
    J<B
    O<D
    P<K
    T<L
    E<D
    T<R
    R<L
    H<B
    F<L
    I<Q
    E<R
    P<M
    S<R
    T<C
    G<Q
    I<N
    G<C
    I<E
    R<N
    A<Q
    Q<M
    B<K
    A<R
    Q<R
    P<B
    E<N
    D<Q
    K<D
    S<F
    B<C
    B<T
    O<J
    S<M
    B<F
    R<M
    S<I
    S<T
    I<F
    H<D
    A<E
    P<T
    E<Q
    C<R
    K<C
    S<H
    B<L
    H<P
    E<F
    A<N
    O<B
    5 10
    D<C
    B<E
    B<D
    E<C
    A<E
    D<E
    A<B
    A<D
    A<C
    B<C
    10 20
    D<J
    C<A
    A<I
    J<G
    F<H
    F<J
    E<G
    F<D
    E<H
    C<J
    C<H
    E<J
    C<B
    D<G
    E<D
    F<G
    F<E
    A<H
    A<D
    J<H
    6 11
    A<B
    C<F
    B<F
    D<B
    B<E
    C<D
    A<F
    C<E
    F<E
    D<E
    A<C
    9 23
    I<A
    C<D
    B<D
    G<B
    F<D
    C<G
    I<F
    H<A
    C<E
    I<H
    B<A
    C<B
    I<E
    G<D
    H<C
    I<C
    D<E
    I<G
    B<F
    I<D
    H<G
    H<D
    C<F
    20 34
    J<C
    L<A
    S<D
    P<I
    R<I
    T<E
    L<O
    T<C
    O<C
    D<O
    S<I
    I<D
    B<G
    F<M
    T<M
    B<C
    H<M
    F<P
    Q<I
    F<O
    Q<J
    R<M
    E<M
    S<N
    B<N
    P<C
    L<E
    H<I
    D<C
    R<S
    Q<N
    P<E
    I<T
    E<D
    20 190
    B<E
    C<M
    N<S
    N<R
    O<K
    M<J
    B<J
    F<B
    G<B
    R<O
    Q<T
    Q<G
    D<G
    M<F
    C<T
    H<E
    D<B
    Q<F
    S<K
    A<P
    H<O
    H<S
    H<I
    P<S
    F<E
    F<T
    M<O
    A<O
    A<J
    R<K
    D<K
    H<N
    M<K
    Q<N
    P<E
    S<O
    P<O
    F<J
    N<D
    F<S
    C<D
    D<O
    A<S
    C<B
    Q<J
    F<P
    M<G
    R<J
    N<O
    L<I
    I<K
    B<O
    J<E
    C<J
    H<T
    Q<A
    Q<S
    L<B
    K<T
    O<T
    A<G
    H<G
    C<R
    P<B
    H<Q
    C<E
    A<E
    I<J
    R<F
    M<D
    H<D
    N<T
    C<O
    I<T
    D<R
    C<K
    H<P
    C<I
    C<P
    N<A
    R<B
    H<M
    R<I
    C<Q
    I<E
    Q<I
    Q<D
    C<S
    D<L
    N<B
    Q<K
    C<G
    P<J
    C<A
    J<T
    Q<L
    D<P
    R<G
    S<T
    H<K
    I<O
    D<E
    I<B
    P<K
    K<E
    N<G
    C<F
    M<T
    S<B
    A<K
    S<E
    A<F
    A<T
    P<G
    R<E
    D<I
    F<K
    I<S
    G<J
    H<F
    G<S
    L<F
    P<I
    M<L
    G<I
    N<P
    B<T
    L<P
    J<K
    C<H
    B<K
    A<I
    G<E
    G<T
    N<M
    M<B
    H<R
    D<J
    M<E
    F<G
    Q<M
    D<S
    H<B
    N<J
    Q<E
    G<O
    C<N
    H<A
    P<T
    Q<B
    L<S
    R<S
    N<L
    L<G
    Q<R
    F<O
    A<R
    L<E
    Q<P
    E<T
    M<R
    M<S
    L<O
    A<L
    R<P
    H<J
    L<K
    M<P
    A<M
    L<T
    R<T
    L<R
    S<J
    N<E
    F<I
    A<D
    D<F
    Q<O
    J<O
    O<E
    C<L
    A<B
    N<K
    N<F
    G<K
    D<T
    N<I
    H<L
    M<I
    L<J
    0 0

## 运行结果： ##

Sorted sequence determined after 6 relations: DCAB.
    Sorted sequence determined after 29 relations: CFDAEBHGJI.
    Sorted sequence cannot be determined.
    Inconsistency found after 48 relations.
    Sorted sequence determined after 318 relations: GMNVKCHFOBRJDZLPXAYSEIWQTU.
    Sorted sequence determined after 25 relations: ABCDEFGHIJKLMNOPQRSTUVWXYZ.
    Sorted sequence determined after 7 relations: BADCE.
    Sorted sequence determined after 158 relations: HNAMGIPCTBJFRLEODKSQ.
    Inconsistency found after 35 relations.
    Sorted sequence cannot be determined.
    Sorted sequence determined after 7 relations: ABDEC.
    Sorted sequence cannot be determined.
    Sorted sequence determined after 11 relations: ACDBFE.
    Sorted sequence cannot be determined.
    Sorted sequence cannot be determined.
    Sorted sequence determined after 179 relations: CHQNAMDLRFPGISBJOKET.

[East Central North America 2001]: http://poj.org/searchproblem?field=source&key=East+Central+North+America+2001