/home/toolbox/public_html/solutions/4/459/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 <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 sz; /* size (number of graph points) */
35 char line[81]; /* buffer used to read line in */
36
37 void init()
38 {
39 /* FUNCTION init */
40 scanf("%d ", &numberOfTimes);
41 } /* FUNCTION init */
42
43 void clear(int x)
44 {
45 /* FUNCTION clear */
46 int i;
47
48 used[0] = 0;
49 list[0] = 0;
50 for (i=1; x>=i; i++)
51 {
52 /* for each row */
53 used[i] = 1;
54 list[i] = i;
55 } /* for each row */
56 for (i=x+1; MAX_DIM>i; i++)
57 {
58 /* for each row */
59 used[i] = 0;
60 list[i] = 0;
61 } /* for each row */
62 } /* FUNCTION clear */
63
64 void dump()
65 {
66 /* FUNCTION dump */
67 int i;
68
69 for (i=1; sz>=i; i++)
70 {
71 printf("%d ", list[i]);
72 }
73 printf(" ");
74 for (i=1; sz>=i; i++)
75 {
76 printf("%d ", used[i]);
77 }
78 printf("\n");
79 } /* FUNCTION dump */
80
81 int cnvrt(char a)
82 {
83 /* FUNCTION cnvrt */
84 return (a - 'A' + 1);
85 } /* FUNCTION cnvrt */
86
87 void connect(int i, int j)
88 {
89 /* FUNCTION connect */
90 int k;
91 int tmp;
92
93 DEBUG printf("connect i=%d (keep) j=%d (lose) \n", i, j);
94 /* are they already connected>? */
95 if (list[i] != list[j])
96 {
97 /* not same -- need to equal them out */
98 used[list[j]] = 0;
99 tmp = list[j];
100 for (k=1; sz>=k; k++)
101 {
102 /* check each item in the list */
103 if (list[k] == tmp)
104 {
105 /* keep list of i */
106 DEBUG printf("B sz = %d list[%d] = %d list[%d] = %d\n", sz, k, list[k], i, list[i]);
107 list[k] = list[i];
108 DEBUG printf("A sz = %d list[%d] = %d list[%d] = %d\n", sz, k, list[k], i, list[i]);
109 } /* keep list of i */
110 } /* check each item in the list */
111 } /* not same -- need to equal them out */
112 } /* FUNCTION connect */
113
114 void getInput()
115 {
116 /* FUNCTION getInput */
117 int i;
118 int j;
119 int tmp;
120
121 fgets(line, 80, stdin);
122 sz = cnvrt(line[0]);
123 clear(sz); /* need to know which letters are used */
124 tmp = (NULL != fgets(line, 80, stdin));
125 line[strlen(line)-1] = 0;
126 DEBUG printf("line = [%s] tmp = %d\n", line, tmp);
127 DEBUG dump();
128 while ((tmp) && (strlen(line) > 0))
129 {
130 /* another line to process */
131 i = cnvrt(line[0]);
132 j = cnvrt(line[1]);
133 connect(i,j);
134 DEBUG dump();
135 tmp = (NULL != fgets(line, 80, stdin));
136 line[strlen(line)-1] = 0;
137 if (!tmp)
138 {
139 line[0] = 0; /* blank line/EOF hack */
140 }
141 DEBUG printf("line = [%s] tmp = %d\n", line, tmp);
142 } /* another line to process */
143 } /* FUNCTION getInput */
144
145 void process()
146 {
147 /* FUNCTION process */
148 int i;
149 int tot = 0;
150
151 for (i=1; sz>=i; i++)
152 {
153 /* process used */
154 tot = tot + used[i];
155 } /* process used */
156 printf("%d\n", tot);
157 } /* FUNCTION process */
158
159 int main()
160 {
161 /* main */
162 int i;
163
164 init();
165 for (i=0; i<numberOfTimes; i++)
166 {
167 /* while */
168 if (0 != i)
169 {
170 printf("\n");
171 }
172 getInput();
173 process();
174 } /* while */
175
176 return EXIT_SUCCESS;
177 } /* main */
178
179