/home/toolbox/public_html/solutions/109/10926/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
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 DEBUG printf("cnt = %d tasks[%d][%d] = %d tasks[%d][%d] = %d\n", cnt, i, k, tasks[i][k], j, k, tasks[j][k]);
136 if ((0 == tasks[i][k]) && (1 == tasks[j][k]))
137 {
138 /* a change */
139 DEBUG printf(" tasks[%d][%d] being set to 1\n", i, k, tasks[i][k]);
140 tasks[i][k] = 1;
141 cnt++;
142 } /* a change */
143 } /* look for indirects */
144 } /* found an dependency */
145 } /* for each possible dependency */
146 } /* for each task */
147 } /* while changes are being made */
148
149 } /* FUNCTION indirect */
150
151 void process()
152 {
153 /* FUNCTION process */
154 int i;
155 int j;
156 int mx;
157
158 DEBUG dump();
159 /* resolve indirect */
160 indirect();
161 DEBUG dump();
162 /* sum dependencies */
163 sum();
164 DEBUG dump();
165 /* find max */
166 mx = 1; /* start with first */
167 for (i=2; numTasks>=i; i++)
168 {
169 /* for each task */
170 mx = (tasks[mx][0] < tasks[i][0]) ? i : mx ;
171 } /* for each task */
172 /* dump out first max */
173 printf("%d\n", mx);
174 } /* FUNCTION process */
175
176 int main()
177 {
178 /* main */
179 int moreToDo;
180
181 moreToDo = getInput();
182 while (moreToDo)
183 {
184 /* while */
185 process();
186 moreToDo = getInput();
187 } /* while */
188
189 return EXIT_SUCCESS;
190 } /* main */
191