/home/toolbox/public_html/solutions/105/10583/b.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 (0)
14
15 /*
16 * Author:
17 * Date:
18 * Purpose:
19 * Problem: 10583
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAXPEOPLE 500001
27
28 int ary[MAXPEOPLE];
29 int m, n;
30 int caseNum = 0;
31
32 int init()
33 {
34 /* FUNCTION init */
35 int i;
36
37 for (i = 0; i < MAXPEOPLE; i ++)
38 {
39 ary[i] = 0;
40 }
41 } /* FUNCTION init */
42
43 int dump()
44 {
45 /* FUNCTION dump */
46 int i;
47 for (i = 1; i <= n; i ++)
48 {
49 printf("%d ", ary[i]);
50 }
51 printf("\n");
52 } /* FUNCTION dump */
53
54 int getInput()
55 {
56 /* FUNCTION getInput */
57 int dataReadFlag;
58 caseNum++;
59 scanf(" %d %d", &n, &m);
60 dataReadFlag = (0 != m || 0 != n);
61 return (dataReadFlag);
62 } /* FUNCTION getInput */
63
64
65 void recurse (int r, int same)
66 {
67 /* FUNCTION recurse */
68 if (0 > ary[r] && ary[r] != same)
69 {
70 recurse(-1*ary[r], same);
71 }
72 ary[r] = same;
73 } /* FUNCTION recurse */
74
75 void process()
76 {
77 /* FUNCTION process */
78 int i;
79 int smaller;
80 int larger;
81 int temp;
82 int count = 0;
83
84 /*Assume 0 means untouched
85 *
86 *case 1: Both ary locations 0,
87 ary[smaller] = smaller, ary[larger] = -1 * smaller
88 *case 2: ary of smaller is 0, ary of larger is non-zero
89 ary[smaller] = -1 * |ary[larger]|;
90 *case 3: ary of larger is 0, ary of smaller is non-zero
91 ary[larger] = -1 * |ary[smaller]|;
92 *case 4: ary of larger is negative, ary of smaller is non-zero
93 recurse(larger)
94 ary[larger] = -1*ary[smaller];
95 *case 5: ary of larger is positive, ary of smaller is negative
96 recurse(smaller)
97 ary[smaller] = -1*ary[larger];
98 *case 6: ary of larger is positive, ary of smaller is positive
99 ary[larger] = -1*ary[smaller];
100 */
101 for (i = 0; i < m; i ++)
102 {
103 scanf(" %d %d", &smaller, &larger);
104 DEBUG printf(" %d %d", smaller, larger);
105 if (smaller > larger)
106 {
107 temp = larger;
108 larger = smaller;
109 smaller = temp;
110 }
111 DEBUG printf(" %d %d\n", smaller, larger);
112
113 if (0 == ary[smaller])
114 {
115 /*cases 1 and 2*/
116 if (0 == ary[larger])
117 {
118 /*case 1*/
119 ary[smaller] = smaller;
120 ary[larger] = -1*smaller;
121 }/*case 1*/
122 else
123 {
124 /*case 2*/
125 ary[smaller] = -1 * abs(ary[larger]);
126 }/*case 2*/
127 }/*cases 1 and 2*/
128 else if (0 == ary[larger])
129 {
130 /*case 3*/
131 ary[larger] = -1 * abs(ary[smaller]);
132 }/*case 3*/
133 else if (0 > ary[larger])
134 {
135 /*case 4*/
136 recurse(larger, -1 * abs(ary[smaller]));
137 if(0 > ary[smaller])
138 {
139 recurse(smaller, ary[smaller]);
140 }
141 }/*case 4*/
142 else if (0 < ary[larger])
143 {
144 /*cases 5 and 6*/
145 if (0 > ary[smaller])
146 {
147 /*case 5*/
148 recurse(smaller, -1 * abs(ary[larger]));
149 }/*case 5*/
150 else
151 {
152 /*case 6*/
153 ary[larger] = -1*ary[smaller];
154 }/*case 6*/
155 }/*cases 5 and 6*/
156 DEBUG dump();
157 }
158
159
160 for (i = 1; i <= n; i ++)
161 {
162 if (0 <= ary[i])
163 {
164 count ++;
165 }
166 }
167 printf("Case %d: %d\n", caseNum, count);
168 } /* FUNCTION process */
169
170 int main ()
171 {
172 /* main */
173 int moreToDo;
174
175 init();
176 moreToDo = getInput();
177 while (moreToDo)
178 {
179 /* while */
180 process();
181 moreToDo = getInput();
182 init();
183 } /* while */
184
185 return EXIT_SUCCESS;
186 } /* main */
187