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