#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define db(a) cout << #a << " = " << a << endl #define db2(a, b) cout << #a << " = " << a << " = " << #b << " = " << b << endl using namespace std; int vis[26], mapa[26][26], top; void buscar(int i) { if (!vis[i]) { vis[i] = 1; for (int j = 0; j <= top; j++) { if (mapa[i][j]) { mapa[i][j] = 0; mapa[j][i] = 0; buscar(j); } } } } int main() { int cases, res; char linea[3]; scanf("%d\n\n", &cases); for (int k = 0; k < cases; k++) { memset(mapa, 0, sizeof mapa); memset(vis, 0, sizeof vis); res = 0; while(gets(linea) && linea[0]) { if (!linea[1]) top = linea[0] - 'A'; else mapa[linea[0] - 'A'][linea[1] - 'A'] = mapa[linea[1] - 'A'][linea[0] - 'A'] = 1; } for (int i = 0; i <= top; i++) if (!vis[i]) buscar(i), res++; printf("%d\n", res); if (k + 1 != cases) printf("\n"); } return 0; }
jueves, 27 de octubre de 2011
459 - Graph Connectivity, uva
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario