Sorting It All Out
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 30110 | Accepted: 10411 |
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.
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.
题意：这题题意好蛋疼啊！！！一个一个给边，一个一个的判断，先判断是否有环。然后再判断是否确定序列。最后前两者都不满足，则此序列不确定。
收获：1.知道只有有环时才k<n。2.入度为0的点不唯一，则此序列不确定。3.入度很重要。
下面是能AC代码，但是 0 0会有问题，不知道为什么?还请各位指教。
#include <cstdio> #include <iostream> //#include <cstdlib> #include <algorithm> #include <ctime> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> using namespace std; const int INF=0x3f3f3f3f; const double eps=1e-10; const double PI=acos(-1.0); const int maxn=5000; struct Edge { int u, v, next; }; Edge edge[maxn]; int head[maxn]; int num, n,m; void init_edge() { num = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[num].u = u; edge[num].v = v; edge[num].next = head[u]; head[u] = num++; } int ans; int topo[maxn]; int in[maxn]; int topsort() { queue<int> q; int indeg[26]; for(int i = 65; i < 65+n; i++) { indeg[i] = in[i]; if(indeg[i] == 0) q.push(i); } int k = 0; int flag=0; while(!q.empty()) { if(q.size()>1) flag = 1; int u = q.front(); q.pop(); topo[k++] = u; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; indeg[v]--; if(indeg[v]==0) q.push(v); } } if(k < n) return 0; if(flag) return -1; else return 1; } char s[5]; int main() { while(~scanf("%d%d", &n, &m)) { if(n==0 && m==0) break; init_edge(); memset(in, 0, sizeof(in)); int flag2 = 0; int flag3 = 0; for(int j = 1; j <= m; j++) { scanf("%s",s); if(!flag2&&!flag3) { in[s[2]]++; addedge(s[0],s[2]); int res = topsort(); if(res == 0) { printf("Inconsistency found after %d relations. ", j); flag2 = 1; } if(res == 1) { printf("Sorted sequence determined after %d relations: ", j); for(int i=0; i < n; i++) printf("%c", topo[i]); printf(". "); flag3 = 1; } } } if(!flag2&&!flag3) puts("Sorted sequence cannot be determined."); //puts("QAQ"); } return 0; }