/home/toolbox/public_html/solutions/4/459/c.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 fgets(line, 80, stdin);
130 sz = cnvrt(line[0]);
131 tmp = (NULL != fgets(line, 80, stdin));
132 line[strlen(line)-1] = 0;
133 DEBUG printf("line = [%s] tmp = %d\n", line, tmp);
134 while ((tmp) && (strlen(line) > 0))
135 {
136 /* another line to process */
137 i = cnvrt(line[0]);
138 j = cnvrt(line[1]);
139 connect(i,j);
140 tmp = (NULL != fgets(line, 80, stdin));
141 line[strlen(line)-1] = 0;
142 if (!tmp)
143 {
144 line[0] = 0; /* blank line/EOF hack */
145 }
146 DEBUG printf("line = [%s] tmp = %d\n", line, tmp);
147 } /* another line to process */
148
149 } /* FUNCTION getInput */
150
151 void process()
152 {
153 /* FUNCTION process */
154 int i;
155 int tot = 0;
156
157 for (i=0; sz>=i; i++)
158 {
159 /* process used */
160 tot = tot + used[i];
161 } /* process used */
162 printf("%d\n", tot);
163 } /* FUNCTION process */
164
165 int main()
166 {
167 /* main */
168 int i;
169
170 init();
171 for (i=0; i<numberOfTimes; i++)
172 {
173 /* while */
174 if (0 != i)
175 {
176 printf("\n");
177 }
178 getInput();
179 process();
180 } /* while */
181
182 return EXIT_SUCCESS;
183 } /* main */
184
185