当前位置:编程学习 > C/C++ >>

POJ 1094 Sorting It All Out (拓扑排序) - from lanshui_Yang

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和m , n 表示26个大写英文子母中的前 n 个字母, m 表示以下m个形如:A < B 的表达式。按照这 m 个表达式给出的顺序,每给出一个表达式(假设序号为k ,1 <= k <= m),就以这前k个表达式为条件,判断以下三种情况:
1、前n个大写英文字母 能 按拓扑序排好 ,并且 只有一种 排列方式。注意:此时k 可能小于 n !!这时输出:Sorted sequence determined after xxx relations: yyy...y. 
2、前n个大写英文字母 能 按拓扑序排好 ,但有 不止一种 排列方式。注意:此时k 必须等于 n !!这时输出:Sorted sequence cannot be determined. 
3、如果不能完成拓扑序,注意:此时k 可能小于 n !!就输出:Sorted sequence cannot be determined.
    解题思路:每给出一个表达式,就以这个表达式以及这个表达式以前的表达式为条件,进行拓扑排序。
    请看代码:
 
#include<iostream>  
#include<cstring>  
#include<string>  
#include<algorithm>  
#include<cmath>  
#include<cstdio>  
#include<vector>  
#define mem(a , b) memset(a , b , sizeof(a))  
using namespace std ;  
const int MAXN = 100 ;  
int ind[MAXN] ;  
int idtmp[MAXN] ;  
char ans[MAXN] ;  
vector<int> G[MAXN] ;  
int n , m ;  
void chu()  
{  
    mem(ind , 0) ;  
    mem(idtmp , 0) ;  
    mem(ans , 0) ;  
    int i ;  
    for(i = 0 ; i <= n ; i ++)  
    G[i].clear() ;  
}  
int topo()  
{  
    int i ;  
    mem(idtmp , 0) ;  
    for(i = 0 ; i < n ; i ++)  
    {  
        idtmp[i] = ind[i] ;  
    }  
    int k = 0 ;  
    int sumd0  ;  
    int u , v ;  
    bool flag1 , flag2 , flag3 ;  
    flag2 = false ;  
    flag3 = true ;  
    for(k = 0 ; k < n ; k ++)  
    {  
        sumd0 = 0 ;  
        for(i = 0 ; i < n ; i ++)  
        {  
            if(idtmp[i] == 0)  
            {  
                sumd0 ++ ;  
                u = i ;  
            }  
        }  
        if(sumd0 > 0)  
        {  
            ans[k] = u + 'A';  
            idtmp[u] -- ;  
            for(int j = 0 ; j < G[u].size() ; j ++)  
            {  
                v = G[u][j] ;  
                idtmp[v] -- ;  
            }  
            if(sumd0 > 1)  
            {  
                flag2 = true ;  
            }  
        }  
        else  
        {  
            flag3 = false ;  
            break ;  
        }  
    }  
    if(!flag3)  
    {  
        return 3 ;  
    }  
    else  
    {  
        if(flag2)  
        {  
            return 2 ;  
        }  
        else  
        {  
            return 1 ;  
        }  
    }  
}  
void init()  
{  
    chu() ;  
    int i ;  
    char a , op , b ;  
    bool f = false ;  
    for(i = 0 ; i < m ; i ++)  
    {  
        cin >> a >> op >> b ;  
        if(f)  
        continue ;  
        int ta , tb ;  
        ta = a - 'A' ;  
        tb = b - 'A' ;  
        G[ta].push_back(tb) ;  
        ind[tb] ++ ;  
        int pan ;  
        pan = topo() ;  
        if(pan == 3)  
        {  
            f = true ;  
            printf("Inconsistency found after %d relations.\n" , i + 1) ;  
        }  
        else if(pan == 1)  
        {  
            ans[n] = '\0' ;  
            f = true ;  
            printf("Sorted sequence determined after %d relations: %s.\n" , i + 1 , ans) ;  
        }  
        else if(pan == 2 && i == m - 1)  
        {  
            puts("Sorted sequence cannot be determined.") ;  
        }  
    }  
}  
int main()  
{  
    while (scanf("%d%d" , &n , &m) != EOF)  
    {  
        if(n == 0 && m == 0)  
        break ;  
        init() ;  
    }  
    return 0 ;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,