Uva 539 The Settlers of Catan

  The Settlers of Catan 

简单题，感觉回溯的最大的一个特点就是在其中一次递归的过程中修改变量后要恢复原状，而且过程跟DFs类似，思路明白了就好做了，这题也一样，题目说找一条最长的路，每两个节点的路径只能走一次，节点可以走多次，我是将将有路径的节点标记好，走过后将这条路径删掉，然后遍历回来的再把这条路恢复，走到一节点该节点没有路径可走的时候判断是否为最长

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=480

#include<stdio.h>
#include<string.h>
#define MAXN 30

int matrix[MAXN][MAXN];
int max;

int Traverse(int cur, int n, int m, int cnt)
{
    int i, j, flag = 0;
    for(i=0; i<n; ++i)
    {
        if(matrix[cur][i] == 1)
        {
            flag = 1;
            matrix[cur][i] = matrix[i][cur] = 0;
            Traverse(i, n, m, cnt+1);
            matrix[cur][i] = matrix[i][cur] = 1;
        }
    }
    if(!flag) max = max > cnt ? max : cnt;
    return 0;
}

int main()
{
    int i, n, m, from, to, cnt = 0;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(!n && !m) break;
        max = 0;
        memset(matrix, -1, sizeof(matrix));
        for(i=0; i<m; ++i)
        {
            scanf("%d%d", &from, &to);
            matrix[from][to] = matrix[to][from] = 1;
        }
        for(i=0; i<n; ++i)
        {
            cnt = 0;
            Traverse(i, n, m, cnt);
        }
        printf("%d\n", max);
    }
    return 0;
}