Photolog

Through the Looking-Glass
2010-10-12: Through the Looking-Glass
My radio speaks is binary!
2010-10-10: My radio speaks is binary!
Gigaminx: (present for my birthday)
2010-09-16: Gigaminx: (present for my birthday)
Trini on bike
2010-09-05: Trini on bike
Valporquero
2010-08-28: Valporquero
My new bike!
2010-08-22: My new bike!
Mario and Ana's wedding
2010-08-13: Mario and Ana's wedding
Canyoning in Guara
2010-08-07: Canyoning in Guara
Trini and Mari in Marbella
2010-08-05: Trini and Mari in Marbella
Trini and Chelo in Tabarca
2010-08-03: Trini and Chelo in Tabarca
Valid XHTML 1.1
Log in
Back to list of problems

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