/home/toolbox/public_html/solutions/109/10926/c.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
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2018-03-18
18 * Purpose: fun
19 * Problem: 10926 - How Many Dependencies?
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define TASK_LIMIT 102
27
28 int numTasks;
29 int tasks[TASK_LIMIT][TASK_LIMIT];
30
31 void init(int x)
32 {
33 /* FUNCTION init */
34 int i;
35 int j;
36
37 for (i=0; x>=i; i++)
38 {
39 /* for each row */
40 for (j=0; x>=j; j++)
41 {
42 /* for each column */
43 tasks[i][j] = 0;
44 } /* for each column */
45 } /* for each row */
46 } /* FUNCTION init */
47
48 void dump()
49 {
50 /* FUNCTION dump */
51 int i;
52 int j;
53
54 for (i=1; numTasks>=i; i++)
55 {
56 /* for each i */
57 for (j=0; numTasks>=j; j++)
58 {
59 /* for each column */
60 printf("%4d", tasks[i][j]);
61 } /* for each column */
62 printf("\n");
63 } /* for each i */
64 printf("\n");
65 } /* FUNCTION dump */
66
67 int getInput()
68 {
69 /* FUNCTION getInput */
70 int dataReadFlag;
71 int i;
72 int j;
73 int cnt;
74 int dep;
75
76 scanf(" %d ", &numTasks);
77 init(numTasks);
78 for (i=1; numTasks>=i; i++)
79 {
80 /* for each task */
81 scanf(" %d ", &cnt);
82 tasks[i][0] = 0;
83 for (j=1; cnt>=j; j++)
84 {
85 /* for each dependency */
86 scanf(" %d ", &dep);
87 tasks[i][dep] = 1;
88 } /* for each dependency */
89 } /* for each task */
90 dataReadFlag = (0 < numTasks);
91 return (dataReadFlag);
92 } /* FUNCTION getInput */
93
94 void sum()
95 {
96 /* FUNCTION sum */
97 int i;
98 int j;
99
100 for (i=1; numTasks>=i; i++)
101 {
102 /* for each task */
103 for (j=1; numTasks>=j; j++)
104 {
105 /* for each possible dependency */
106 tasks[i][0] = tasks[i][0] + tasks[i][j];
107 } /* for each possible dependency */
108 } /* for each task */
109 } /* FUNCTION sum */
110
111 void indirect()
112 {
113 /* FUNCTION indirect */
114 int cnt = 1;
115 int i;
116 int j;
117 int k;
118
119 while (0 < cnt)
120 {
121 /* while changes are being made */
122 cnt = 0;
123 for (i=1; numTasks>=i; i++)
124 {
125 /* for each task */
126 for (j=1; numTasks>=j; j++)
127 {
128 /* for each possible dependency */
129 if (0 != tasks[i][j])
130 {
131 /* found an dependency */
132 for (k=1; numTasks>k; k++)
133 {
134 /* look for indirects */
135 if ((0 == tasks[i][k]) && (1 == tasks[j][k]))
136 {
137 /* a change */
138 tasks[i][k] = 1;
139 cnt++;
140 } /* a change */
141 } /* look for indirects */
142 } /* found an dependency */
143 } /* for each possible dependency */
144 } /* for each task */
145 } /* while changes are being made */
146
147 } /* FUNCTION indirect */
148
149 void process()
150 {
151 /* FUNCTION process */
152 int i;
153 int j;
154 int mx = 0;
155
156 DEBUG dump();
157 /* resolve indirect */
158 indirect();
159 DEBUG dump();
160 /* sum dependencies */
161 sum();
162 DEBUG dump();
163 /* find max */
164 for (i=1; numTasks>=i; i++)
165 {
166 /* for each task */
167 mx = (mx > tasks[i][0]) ? mx : tasks[i][0];
168 } /* for each task */
169 /* dump out first max */
170 for (i=1; numTasks>=i; i++)
171 {
172 /* for each task */
173 if (mx == tasks[i][0])
174 {
175 /* find first max */
176 printf("%d\n", i);
177 numTasks = 0;
178 } /* find first max */
179 } /* for each task */
180 } /* FUNCTION process */
181
182 int main()
183 {
184 /* main */
185 int moreToDo;
186
187 moreToDo = getInput();
188 while (moreToDo)
189 {
190 /* while */
191 process();
192 moreToDo = getInput();
193 } /* while */
194
195 return EXIT_SUCCESS;
196 } /* main */
197