题目：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; }