jueves, 27 de octubre de 2011

459 - Graph Connectivity, uva

#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;
}

No hay comentarios:

Publicar un comentario