/home/toolbox/public_html/solutions/4/459/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 <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /* fprintf(stderr, "functionName: message", varslist); */
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2018-03-14
20 * Purpose: fun
21 * Problem: 459 - Graph Connecttivity
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define MAX_DIM 28
29 #define UNCONNECTED 0
30
31 int numberOfTimes; /* number of cases */
32 int list[MAX_DIM]; /* list to hold connections */
33 int used[MAX_DIM]; /* keep track of unique subgraphs */
34 int usedMax; /* what is largest used */
35 int sz; /* size (number of graph points) */
36 char line[81]; /* buffer used to read line in */
37
38 void init()
39 {
40 /* FUNCTION init */
41 scanf("%d ", &numberOfTimes);
42 } /* FUNCTION init */
43
44 void clear()
45 {
46 /* FUNCTION clear */
47 int i;
48
49 usedMax = 0;
50 for (i=0; MAX_DIM>i; i++)
51 {
52 /* for each row */
53 used[i] = 0;
54 list[i] = 0;
55 } /* for each row */
56 } /* FUNCTION clear */
57
58 void dump()
59 {
60 /* FUNCTION dump */
61 } /* FUNCTION dump */
62
63 int cnvrt(char a)
64 {
65 /* FUNCTION cnvrt */
66 return (a - 'A' + 1);
67 } /* FUNCTION cnvrt */
68
69 void connect(int i, int j)
70 {
71 /* FUNCTION connect */
72 int k;
73
74 if (UNCONNECTED == list[i])
75 {
76 /* i has never been connected before */
77 if (UNCONNECTED == list[j])
78 {
79 /* J has never been connected either */
80 usedMax++;
81 used[usedMax] = 1;
82 list[i] = usedMax;
83 list[j] = usedMax;
84 } /* J has never been connected either */
85 else
86 {
87 /* j is connected but i is not */
88 list[i] = list[j];
89 } /* j is connected but i is not */
90 } /* i has never been connected before */
91 else
92 {
93 /* i is connected */
94 if (UNCONNECTED == list[j])
95 {
96 /* i connected but j not */
97 list[j] = list[i];
98 } /* i connected but j not */
99 else
100 {
101 /* both are connected */
102 if (list[i] != list[j])
103 {
104 /* not same -- need to equal them out */
105 for (k=1; sz>=k; k++)
106 {
107 /* check each item in the list */
108 used[j] = 0;
109 if (list[k] == list[j])
110 {
111 /* keep list of i */
112 list[k] = list[i];
113 } /* keep list of i */
114 } /* check each item in the list */
115 } /* not same -- need to equal them out */
116 } /* both are connected */
117 } /* i is connected */
118
119 } /* FUNCTION connect */
120
121 void getInput()
122 {
123 /* FUNCTION getInput */
124 int i;
125 int j;
126 int tmp;
127
128 clear();
129 scanf("%s", line); /* get "count" */
130 sz = cnvrt(line[0]);
131 tmp = scanf("%s", line);
132 printf("line = [%s] tmp = %d\n", line, tmp);
133 while ((strlen(line) > 0))
134 {
135 /* another line to process */
136 i = cnvrt(line[0]);
137 j = cnvrt(line[1]);
138 connect(i,j);
139 tmp = scanf("%s", line);
140 if (0 > tmp)
141 {
142 line[0] = 0; /* blank line/EOF hack */
143 }
144 printf("line = [%s] tmp = %d\n", line, tmp);
145 } /* another line to process */
146
147 } /* FUNCTION getInput */
148
149 void process()
150 {
151 /* FUNCTION process */
152 int i;
153 int tot = 0;
154
155 for (i=0; sz>=i; i++)
156 {
157 /* process used */
158 tot = tot + used[i];
159 } /* process used */
160 printf("%d\n", tot);
161 } /* FUNCTION process */
162
163 int main()
164 {
165 /* main */
166 int i;
167
168 init();
169 for (i=0; i<numberOfTimes; i++)
170 {
171 /* while */
172 if (0 != i)
173 {
174 printf("\n");
175 }
176 getInput();
177 process();
178 } /* while */
179
180 return EXIT_SUCCESS;
181 } /* main */
182
183