Hedge Mazes ACM Latinamerica 2011

# include "stdio.h"
# include "string.h"

# define MAXNODOS 10000

int R, C, Q;

int *graph[ MAXNODOS + 1], ngraph[ MAXNODOS + 1];
int mem[(MAXNODOS + 1)*40], arista[ MAXNODOS * 40 + 1][ 2 ];
int vis[MAXNODOS + 1] , mark[ MAXNODOS + 1], SET[MAXNODOS + 1], posNode[MAXNODOS + 1]; 

int getSet( int node ){ return node == SET[node] ? node : (SET[ node ] = getSet( SET[node])); }

int max( int a, int b ){ return a > b ? a : b; }
int min( int a, int b ){ return a < b ? a : b; }

int componentConection( int node, int level , int father){
  int response = level, x;
  if( vis[ node ] == 1 ) return mark[ node ];
  if( vis[node] == 2) return response;
  mark[ node ] = level;
  posNode[level] = node;
  vis[ node ] = 1;
  for( x = 0; x < ngraph[ node ]; x++) if( graph[node][x] != father ){
     response = min( response, componentConection( graph[node][x], level + 1, node ) );
     SET[ getSet( node )] = getSet( posNode[response]  );
  }
  vis[node] = 2;
  return response;
}

void markSameLine( int node , int value, int father){
  int x;
  if( mark[ node ] > 0 ) return;
  mark[ node ] = value;
  for( x = 0; x < ngraph[ node ] ; x++ ) if( graph[node][x] != father ){
   if( getSet( graph[node][x] ) != getSet( node )  ){
     markSameLine( graph[ node ][ x ], value, node );
   }
  }
}

main(){
  int a, b, x, y, nmem;
  while( scanf("%d %d %d", &R, &C, &Q) != EOF && ( R || C || Q)){
    memset( ngraph, 0, sizeof( ngraph ));
    for( x = 0; x < C; x++){
      scanf("%d %d", &a, &b);
      arista[ x ][ 0 ] = a;
      arista[ x ][ 1 ] = b;
      ngraph[ a ]++;
      ngraph[ b ]++;
    } 
    nmem = 0;
    for( x = 0; x <= R; x++){
      graph[ x ] = mem + nmem;
      nmem += ngraph[ x ];  
    }
    memset( ngraph, 0, sizeof( ngraph ));
    for( x = 0; x < C; x++){
      a = arista[ x ][ 0 ]; 
      b = arista[ x ][ 1 ];
      graph[a][ngraph[a]++] = b; 
      graph[b][ngraph[b]++] = a; 
    }
    memset( vis, 0, sizeof( vis ));
    memset( mark, 0, sizeof( mark ));
    for( x = 0; x <= R; x++) SET[ x ] = x;
    for( x = 1; x <= R; x++)
      if( vis[ x ] == 0 )
         componentConection( x , 0, x ); 
    memset( mark, 0, sizeof( mark ));
    for( x = 1; x <= R; x++) if( mark[ x ] == 0 ){
      markSameLine( x, x, x);
    }
    for( x = 1; x <= Q; x++){
      scanf("%d %d", &a, &b); 
      if( ( mark[ a ] == 0 || mark[b] == 0 ) || mark[ a ] != mark[ b ]) printf("N\n");
      else printf("Y\n");
    }
    printf("-\n");
  }
  return 0; 
}
}//

Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com