/home/toolbox/public_html/solutions/100/10004/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 #define MAX_NODES 202
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2014-11-11
20 * Purpose: fun
21 * Problem: 10004 - Bicoloring
22 */
23
24 /*
25 * This template reads data until a terminating value is reached.
26 */
27
28 int numNodes;
29 int numEdges;
30 int ary[MAX_NODES][MAX_NODES];
31 int colors[MAX_NODES]; /* color of each node (can be 2 or 3) */
32 int done[MAX_NODES]; /* keep track of whether I have tried this nodes neighbors */
33 int swap[4] = {0, 0, 3, 2};
34
35 void init(int k)
36 {
37 /* FUNCTION init */
38 int i;
39 int j;
40
41 for (i=0; i<k; i++)
42 {
43 /* work to do */
44 colors[i] = 0;
45 done[i] = FALSE;
46 for (j=0; j<k; j++)
47 {
48 /* read each edge */
49 ary[i][j] = 0;
50 } /* read each edge */
51 } /* work to do */
52 colors[0] = 2;
53 } /* FUNCTION init */
54
55 void dump()
56 {
57 /* FUNCTION dump */
58 int i;
59 int j;
60
61 printf("node color done\n");
62 for (i=0; i< numNodes; i++)
63 {
64 printf("%4d %3d %6d\n", i, colors[i], done[i]);
65 };
66 printf("\n");
67 for (i=0; i<numNodes; i++)
68 {
69 /* for */
70 printf("%3d: ", i);
71 for (j=0; j<numNodes; j++)
72 {
73 printf("%2d", ary[i][j]);
74 }
75 printf("\n");
76 } /* for */
77 printf("\n");
78 } /* FUNCTION dump */
79
80 int getInput()
81 {
82 /* FUNCTION getInput */
83 int dataReadFlag = TRUE;
84 int i;
85 int t1;
86 int t2;
87
88 scanf(" %d ", &numNodes);
89 if (0 == numNodes)
90 dataReadFlag = FALSE;
91 else
92 {
93 /* work to do */
94 init(numNodes);
95 scanf(" %d ", &numEdges);
96 for (i=0; i<numEdges; i++)
97 {
98 /* read each edge */
99 scanf(" %d %d ", &t1, &t2);
100 ary[t1][t2] = 1;
101 ary[t2][t1] = 1;
102 } /* read each edge */
103 } /* work to do */
104 return (dataReadFlag);
105 } /* FUNCTION getInput */
106
107 int doNode(int r)
108 {
109 /* FUNCTION doNode */
110 int fail = FALSE;
111 int i;
112
113 DEBUG printf(" doNode: %d\n", r);
114 for (i=0; i<numNodes; i++)
115 {
116 /* for each row */
117 DEBUG printf("doNode: ary[%d][%d] = %d\n", r, i, ary[r][i]);
118 if ((1 == ary[r][i]) && (i != r))
119 {
120 /* found an adjacent node */
121 DEBUG printf("doNode: i=%d\n", i);
122 if (colors[r] == colors[i])
123 {
124 /* problem */
125 fail = TRUE;
126 i = numNodes;
127 } /* problem */
128 else
129 {
130 /* node i needs its color set */
131 colors[i] = swap[colors[r]];
132 } /* node i needs its color set */
133 } /* found an adjacent node */
134 } /* for each row */
135 done[r] = TRUE;
136 DEBUG if (fail)
137 {
138 printf("fail\n");
139 }
140 DEBUG dump();
141 DEBUG printf("doNode: leaving\n");
142 return fail;
143 } /* FUNCTION doNode */
144
145 int checkForUndone()
146 {
147 /* FUNCTION checkForUndone */
148 int undone = TRUE;
149 int i;
150
151 for (i=1; i<numNodes; i++)
152 {
153 /* for each node */
154 undone = undone && ! done[i];
155 } /* for each node */
156
157 return undone;
158 } /* FUNCTION checkForUndone */
159
160 void process()
161 {
162 /* FUNCTION process */
163 int i;
164 int j;
165 int fail;
166
167
168 /*
169 0 1 2 3 4
170 0 0 1 1 1 0 2 0 0 0 1 0 0 b
171 0 0 1 0 0 1 2 1 0 0 1 0 0 b
172 1 1 0 0 1 2 3 2 1 1 0 1 0 w
173 1 0 0 0 0 3 3 3 0 0 1 1 1 b
174 1 0 1 0 0 4 3 4 0 0 0 1 0 w
175 */
176 fail = doNode(0);
177 DEBUG dump();
178 while ((! fail) && (checkForUndone()))
179 {
180 /* while more nodes to process */
181 DEBUG printf("process: while \n");
182 for (i=1; i<numNodes; i++)
183 {
184 /* for each node */
185 DEBUG printf("process: for i=%d\n", i);
186 DEBUG dump();
187 if ((0 != colors[i]) && (! done[i]))
188 {
189 /* we know the color of this row and it has not been processed */
190 DEBUG printf("process: call doNode(%d)\n", i);
191 fail = doNode(i);
192 } /* we know the color of this row and it has not been processed */
193 } /* for each node */
194 } /* while more nodes to process */
195 if (fail)
196 {
197 printf("NOT ");
198 }
199 printf("BICOLORABLE.\n");
200 } /* FUNCTION process */
201
202 int main ()
203 {
204 /* main */
205 int moreToDo;
206
207 moreToDo = getInput();
208 while (moreToDo)
209 {
210 /* while */
211 DEBUG dump();
212 process();
213 moreToDo = getInput();
214 } /* while */
215
216 return EXIT_SUCCESS;
217 } /* main */
218