/home/toolbox/public_html/solutions/103/10305/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 20210901
19 * Purpose: fun
20 * Problem: 10305 - Ordering Tasks
21 */
22
23 #define MAX_TASKS 105
24 #define PRINTED -1
25
26 int tasks[MAX_TASKS][MAX_TASKS];
27 /* a 1 in a column indicates that the task comes before that task
28 * the 0th column is a count of dependencies
29 */
30 int n; /* number of tasks */
31 int m; /* number of relationships */
32
33 /*
34 * This template reads data until a terminating value is reached.
35 */
36
37 void init()
38 {
39 /* FUNCTION init */
40 } /* FUNCTION init */
41
42 void dump()
43 {
44 /* FUNCTION dump */
45 int i;
46 int j;
47
48 printf("%d tasks with %d relationships\n", n, m);
49 for (i=1; i<=n; i++)
50 {
51 /* for each task */
52 printf("%3d(%2d): ", i, tasks[i][0]);
53 for (j=1; j<=n; j++)
54 {
55 /* for each task */
56 printf("%2d ", tasks[i][j]);
57 } /* for each task */
58 printf("\n");
59 } /* for each task */
60 printf("\n");
61 } /* FUNCTION dump */
62
63 int getInput()
64 {
65 /* FUNCTION getInput */
66 int dataReadFlag;
67 int i;
68 int j;
69 int bef;
70 int aft;
71
72 scanf(" %d %d ", &n, &m);
73 dataReadFlag = (0 != m) || (0 != n);
74 if (dataReadFlag)
75 {
76 /* initialize task list */
77 for (i=0; n>=i; i++)
78 {
79 /* for each task */
80 tasks[i][0] = 0;
81 for (j=1; n>=j; j++)
82 {
83 /* for each possible precursor */
84 tasks[i][j] = 0;
85 } /* for each possible precursor */
86 } /* for each task */
87 } /* initialize task list */
88 DEBUG dump();
89 for (i=0; i<m; i++)
90 {
91 /* for each relationship */
92 scanf(" %d %d ", &bef, &aft);
93 if (0 == tasks[aft][bef])
94 {
95 /* not set before */
96 tasks[aft][bef] = 1;
97 tasks[aft][0] = tasks[aft][0] + 1;
98 DEBUG printf("(bef %d) (aft %d)\n", bef, aft);
99 DEBUG dump();
100 } /* not set before */
101 } /* for each relationship */
102 return (dataReadFlag);
103 } /* FUNCTION getInput */
104
105 void rst(int x)
106 {
107 /* FUNCTION rst */
108 int i;
109
110 for (i=1; n>=i; i++)
111 {
112 /* for each possible task */
113 if (0 != tasks[i][x])
114 {
115 /* found a prereq */
116 tasks[i][x] = 0;
117 if (0 < tasks[i][0])
118 {
119 /* decrease couont */
120 tasks[i][0] = tasks[i][0] - 1;
121 } /* decrease couont */
122 } /* found a prereq */
123 } /* for each possible task */
124 tasks[x][0] = PRINTED;
125 } /* FUNCTION rst */
126
127 int noPrereq(int x)
128 {
129 /* FUNCTION noPrereq */
130 return (0 == tasks[x][0]);
131 } /* FUNCTION noPrereq */
132
133 int notPrinted(int x)
134 {
135 /* FUNCTION notPrinted */
136 return (PRINTED <= tasks[x][0]);
137 } /* FUNCTION notPrinted */
138
139 int notAllPrinted()
140 {
141 /* FUNCTION notAllPrinted */
142 int i;
143 int tmp = TRUE;
144
145 for (i=1; n>=i; i++)
146 {
147 /* for */
148 DEBUG printf("tasks[%d][0] = %d\n", i, tasks[i][0]);
149 tmp = tmp && (PRINTED == tasks[i][0]);
150 } /* for */
151 return (! tmp);
152 } /* FUNCTION notAllPrinted */
153
154 void process()
155 {
156 /* FUNCTION process */
157 int i;
158 int j;
159 int first = TRUE;
160
161 while (notAllPrinted())
162 {
163 /* while */
164 for (i=1; n>=i; i++)
165 {
166 /* for each task */
167 if (notPrinted(i))
168 {
169 /* task has not been printed yet */
170 if (noPrereq(i))
171 {
172 /* no preReqs -- it can be printed */
173 if (first)
174 {
175 /* first time */
176 first = FALSE;
177 printf("%d", i);
178 } /* first time */
179 else
180 {
181 /* 2 through n */
182 printf(" %d", i);
183 } /* 2 through n */
184 rst(i);
185 } /* no preReqs -- it can be printed */
186 } /* task has not been printed yet */
187 } /* for each task */
188 } /* while */
189 printf("\n");
190 } /* FUNCTION process */
191
192 int main()
193 {
194 /* main */
195 int moreToDo;
196
197 init();
198 moreToDo = getInput();
199 while (moreToDo)
200 {
201 /* while */
202 process();
203 moreToDo = getInput();
204 } /* while */
205
206 return EXIT_SUCCESS;
207 } /* main */
208