/home/toolbox/public_html/solutions/100/10004/j.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 for (i=0; i<numNodes; i++)
114 {
115 /* for each row */
116 if ((1 == ary[r][i]) && (i != r))
117 {
118 /* found an adjacent node */
119 if (colors[r] == colors[i])
120 {
121 /* problem */
122 fail = TRUE;
123 i = numNodes;
124 } /* problem */
125 else
126 {
127 /* node i needs its color set */
128 colors[i] = swap[colors[r]];
129 } /* node i needs its color set */
130 } /* found an adjacent node */
131 } /* for each row */
132 done[r] = TRUE;
133 return fail;
134 } /* FUNCTION doNode */
135
136 int checkForUndone()
137 {
138 /* FUNCTION checkForUndone */
139 int undone = TRUE;
140 int i;
141
142 for (i=1; i<numNodes; i++)
143 {
144 /* for each node */
145 undone = undone && ! done[i];
146 } /* for each node */
147
148 return undone;
149 } /* FUNCTION checkForUndone */
150
151 void process()
152 {
153 /* FUNCTION process */
154 int i;
155 int j;
156 int fail;
157
158
159 /*
160 0 1 2 3 4
161 0 0 1 1 1 0 2 0 0 0 1 0 0 b
162 0 0 1 0 0 1 2 1 0 0 1 0 0 b
163 1 1 0 0 1 2 3 2 1 1 0 1 0 w
164 1 0 0 0 0 3 3 3 0 0 1 1 1 b
165 1 0 1 0 0 4 3 4 0 0 0 1 0 w
166 */
167 fail = doNode(0);
168 while ((! fail) && (checkForUndone()))
169 {
170 /* while more nodes to process */
171 for (i=1; i<numNodes; i++)
172 {
173 /* for each node */
174 if ((0 != colors[i]) && (! done[i]))
175 {
176 /* we know the color of this row and it has not been processed */
177 fail = doNode(i);
178 } /* we know the color of this row and it has not been processed */
179 } /* for each node */
180 } /* while more nodes to process */
181 if (fail)
182 {
183 printf("NOT ");
184 }
185 printf("BICOLORABLE.\n");
186 } /* FUNCTION process */
187
188 int main ()
189 {
190 /* main */
191 int moreToDo;
192
193 moreToDo = getInput();
194 while (moreToDo)
195 {
196 /* while */
197 process();
198 moreToDo = getInput();
199 } /* while */
200
201 return EXIT_SUCCESS;
202 } /* main */
203