Sorting It All Out
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
题目类型：拓扑排序+枚举
算法分析：边读入边求解拓扑序，判断拓扑序是否存在，存在时是否唯一。注意这里要优先判断是否存在，而且唯一拓扑序不一定是按照常规字母表大小规则排列的！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
/************************************************* Author :supermaker Created Time :2016/3/20 8:50:22 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 166; int ind[maxn], tmp[maxn], res, num, n, m; vector <int> edge[maxn]; char ans[maxn]; void Topo (int cnt) { int tot = 0, is_one = 0, len = 0; bool is_valid = true; for (int i = 0; i < n; i++) tmp[i] = ind[i]; queue <int> qu; for (int i = 0; i < n; i++) if (tmp[i] == 0) { qu.push (i); is_one++; } if (is_one >= 2) is_valid = false; while (!qu.empty ()) { int tt = qu.front (); qu.pop (); ans[len++] = (char) (tt + 'A'); tot++, is_one = 0; for (int i = 0; i < edge[tt].size (); i++) { tmp[edge[tt][i]]--; if (tmp[edge[tt][i]] == 0) { qu.push (edge[tt][i]); is_one++; } } if (is_one >= 2) is_valid = false; } if (tot < n) { res = 2; num = cnt; } else { if (!is_valid) { res = 3; return ; } res = 1; num = cnt; for (int i = 0; i < len / 2; i++) { char tc = ans[i]; ans[i] = ans[len-1-i]; ans[len-1-i] = tc; } ans[len] = 0; } } int main() { //CFF; //CPPFF; while (scanf ("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0) break; memset (ind, 0, sizeof (ind)); for (int i = 0; i < maxn; i++) edge[i].clear (); res = -1, num = 1; char cmd[6]; for (int i = 1; i <= m; i++) { scanf ("%s", cmd); ind[cmd[0]-'A']++; edge[cmd[2]-'A'].push_back (cmd[0]-'A'); if (res == -1 || res == 3) Topo (i); } if (res == 1) printf ("Sorted sequence determined after %d relations: %s.\n", num, ans); else if (res == 2) printf ("Inconsistency found after %d relations.\n", num); else puts ("Sorted sequence cannot be determined."); } return 0; } |
- « 上一篇：poj3734
- poj1128：下一篇 »