539 - The Settlers of Catan

題目：539 - The Settlers of Catan

題目大意：給出一系列的點和相應的邊，求最長的路徑，路徑是由相連的邊構成的，每個邊最多被用一次。

階梯思路:回溯，每次都從一個點開始dfs，如果發現走過相同的邊，就把長度記錄下來，然後把狀態恢復，走別的路。最後去這些路徑中最長的。注意：每個點都有可能成為最長路徑的起點。

#include
#include

const int N = 25;
int map[N][N], m, n, max, d[N];

void dfs (int o, int path) {
	
	for (int i = 0; i < n; i++) {
		
		if (map[o][i]) {
			
			map[o][i] = map[i][o] = 0;
//			printf("%d\n", path);
			dfs(i, path + 1);
			map[o][i] = map[i][o] = 1;
		}
	
	}
	if (max < path)
		max = path;

}

int main () {

	while (scanf("%d%d", &n, &m), m || n) {

		memset(map, 0, sizeof(map));
		memset(d, 0, sizeof(d));
		int x, y;
		for (int i = 0; i < m; i++ ) {
			
			scanf("%d%d", &x , &y);
			map[x][y] = map[y][x] = 1;
			d[x]++;
			d[y]++;
		}

		max = 0;
//		int count = 0;
		for (int i = 0; i < n; i++) 
//			if (d[i] == 1) {

				dfs(i, 0);
//				count++;
//			}
//		if (!count) 
//			dfs(x, 0);
		printf("%d\n", max);
	}
	return 0;
}