# 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
No hay comentarios:
Publicar un comentario