road_graph.c

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

static unsigned int graph[21][21] = {{0}};
static unsigned int visited[21] = {0};
static unsigned int nvertices = 0;
static unsigned int nedges = 0;
static unsigned int nsolutions = 0;

void init_graph() {
	if (scanf("%u %u", &nvertices, &nedges) == 2) {
		unsigned int i, from, to;
		
		for (i = 0; i < nedges; i++) {
			if (scanf("%u %u", &from, &to) == 2) {
				graph[from][to] = 1;
				graph[to][from] = 1;
			}
		}
	}
}

void traverse_graph(unsigned int current) {
	unsigned int i;
	
	if (current == nvertices) {
		bool done = true;
		
		for (i = 1; i <= nvertices; i++) {
			if (visited[i] == 0) {
				done = false;
				break;
			}
		}
		
		if (done) {
			nsolutions += 1;
		}
		
		return;
	}
	
	for (i = 1; i <= nvertices; i++) {
		if (graph[current][i] == 1 && visited[i] == 0) {
			visited[i] = 1;
			traverse_graph(i);
			visited[i] = 0;
		}
	}
}

int main(int argc, const char * argv[]) {
	init_graph();
	traverse_graph(1);
	printf("There's %u solutions to this graph.\n", nsolutions);
	return 0;
}