Sorting It All Out
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 19054 |
|
Accepted: 6511 |
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.
我被我自己惡心倒了，這題思路很簡單
就是topsort，但要判斷環
判斷環可以用拓撲排序判斷，如果topsort不能遍歷所有的點就說明存在環
也可以用dfs判斷，如果在dfs過程中遍歷到已經遍歷的節點，那肯定存在環
這里給出個簡單的dfs
1
int dfs(int u)
2
{
3
int ii;
4 if (x==u) return 1;
5 for (ii=1; ii<=num[u] ; ii++ )
6
{
7 if (dfs(map[u][ii])==1)
8 return 1;
9
}
10 return 0;
11
}//x是遍歷的初始節點，這個dfs可以繼續優化
我剛開始想可以topsort之后再判斷環，但是我就被自己惡心到了
我寫的topsort中如果出現不能確定的情況就退出
那么這樣就不知道有沒有環了，
我還用了一個巨惡心的標志flag
這個flag讓我wa了無數次，題目我也不太明白剛開始
我誤以為如果前面幾條能判斷出那三種情況之一的話就不用管后面的了，其實不然，如果目前不確定的話，那還應該繼續判斷下去
直到出現了矛盾（環）或者能確定出唯一的topsort的情況
還有我在查環的時候把dfs過程放在了topsort里面，其實本意是只要查一邊就行了
但是我在寫的時候每個點都dfs一遍，這樣時間就爆了，
不得已，改在init里面了
這道題終于艱難的A掉了
1#include<stdio.h>
2#include<string.h>
3#include<math.h>
4#define MAX 30
5int degree[MAX],degree1[MAX];
6int map[MAX][MAX];
7int num[MAX],stack[MAX],top;
8int n,m,len,flag,ans;
9int seq[27],fff;
10int used,x,y;
11short ff[27];
12void push(int i)
13{
14 top++;
15 stack[top]=i;
16}
17int pop()
18{
19 top--;
20 return stack[top+1];
21}
22int dfs(int u)
23{
24 int ii;
25 if (x==u) return 1;
26 for (ii=1; ii<=num[u] ; ii++ )
27 {
28 if (dfs(map[u][ii])==1)
29 return 1;
30 }
31 return 0;
32}
33void topsort()
34{
35 int i,j,now;
36 len=0;
37 top=0;
38 for (i=1; i<=n ; i++ )
39 if(ff[i]==1&°ree[i]==0)
40 push(i);
41 if (top>1&&used==n)
42 {
43 flag=-1;
44 return;
45 }
46 while (top)
47 {
48 now=pop();
49 len++;
50 seq[len]=now;
51 for (i=1; i<=num[now] ; i++ )
52 {
53 degree[map[now][i]]--;
54 if (degree[map[now][i]]==0)
55 {
56 push(map[now][i]);
57 }
58 if (top>1&&used==n)
59 {
60 flag=-1;
61 return;
62 }
63 }
64 }
65 if (len<used)
66 {
67 flag=1;
68 return;
69 }
70 if (len==n)
71 {
72 flag=2;
73 return;
74 }
75}
76void print()
77{
78 int i;
79 if (flag==1)
80 {
81 printf("Inconsistency found after %d relations.\n",ans);
82 return;
83 }
84 if (flag==-1)
85 {
86 printf("Sorted sequence cannot be determined.\n");
87 return;
88 }
89 if (flag==2)
90 {
91 printf("Sorted sequence determined after %d relations: ",ans);
92 for (i=1; i<=n ; i++ )
93 {
94 printf("%c",seq[i]+64);
95 }
96 printf(".\n");
97 return;
98 }
99}
100void init()
101{
102 char tmp[3];
103 int i,j,a,b;
104 memset(ff,0,sizeof(ff));
105 memset(degree1,0,sizeof(degree1));
106 memset(num,0,sizeof(num));
107 memset(map,0,sizeof(map));
108 flag=0;
109 used=0;
110 for (i=1; i<=m ; i++ )
111 {
112 scanf("%s",&tmp);
113 a=tmp[0]-64;
114 if (!ff[a])
115 {
116 used++;
117 ff[a]=1;
118 }
119 b=tmp[2]-64;
120 if (!ff[b])
121 {
122 used++;
123 ff[b]=1;
124 }
125 x=a;
126 if ((flag==0||flag==-1)&&(dfs(b)==1))
127 {
128 flag=1;
129 ans=i;
130 }
131 if (flag==0||flag==-1)
132 {
133 degree1[b]++;
134 num[a]++;
135 map[a][num[a]]=b;
136 for (j=1; j<=n ; j++ )
137 {
138 degree[j]=degree1[j];
139 }
140 topsort();
141 ans=i;
142 }
143 }
144 if (flag==0&&used<n)
145 {
146 flag=-1;
147 return;
148 }
149}
150int main()
151{
152 scanf("%d%d",&n,&m);
153 while (!(n==0&&m==0))
154 {
155 init();
156 print();
157 scanf("%d%d",&n,&m);
158 }
159 return 0;
160}
161