POJ 1094 Sorting It All Out (拓扑排序) - from lanshui_Yang
DescriptionAn 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++ ,