Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Numbering Paths

125.c

/* 125- Numbering Paths */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXI 35

int inters[MAXI][MAXI];
int routes[MAXI][MAXI];
int maxint;
int visited[MAXI];

void
visit_node(int orig, int node) {
	int i;

	if (visited[node]>=1) {
		routes[orig][node]=-1;
	} else {
		routes[orig][node]++;
	}
	if (visited[node] >= 3) {
		return;
	}
	visited[node]++;
	for(i=0; i<=maxint; i++) {
		if (inters[node][i]) {
			if (visited[node]>=2) {
				visited[i]++;
			}
			visit_node(orig, i);
		}
	}
	visited[node]--;
}

void
calc_routes(void) {
	int i,j;

	for(i=0; i<=maxint; i++) {
		memset(visited, 0, sizeof(visited));
		for(j=0; j<=maxint; j++) {
			if (inters[i][j]) {
				visited[i]=1;
				visit_node(i,j);
			}
		}
	}
}

int
main(void) {
	int a,b,n;
	int i,j;
	int citnum=0;

	while(1) {
		if (scanf("%d", &n)!=1) {
			break;
		}
		maxint=0;
		memset(inters, 0, sizeof(inters));
		memset(routes, 0, sizeof(routes));
		for(i=0; i<n; i++) {
			scanf("%d %d", &a, &b);
			if (a>maxint) {
				maxint=a;
			}
			if (b>maxint) {
				maxint=b;
			}
			inters[a][b] = 1;
		}
		if (maxint > 30) abort();
		printf("matrix for city %d\n", citnum++);
		calc_routes();
		for(i=0; i<=maxint; i++) {
			for(j=0; j<maxint; j++) {
				printf("%d ", routes[i][j]);
			}
			printf("%d\n", routes[i][maxint]);
		}
	}
	return 0;
}