[UAa] 539 The Settlers of Catan.cpp

#include <cstdio>
#include <vector>
using namespace std;
int DFS (int node, vector<int> toNode[30], int dis, bool visit[][30])
{
    int longest_length = 0;            // 當前node能走的最遠距離
    for (int nxt_node : toNode[node]){
        if (!visit[node][nxt_node]) {  // 該條線還沒走過
            visit[node][nxt_node] = 1;
            visit[nxt_node][node] = 1; // 雙向關閉

            int length = DFS (nxt_node, toNode, dis+1, visit);
            if (length > longest_length) longest_length = length;

            visit[node][nxt_node] = 0;
            visit[nxt_node][node] = 0; // 雙向開啟
        }
    }
    if (longest_length == 0) return dis; //如果走到底 回傳當前距離
    else return longest_length;          //否則回傳該點能走的最長距離
}
int main()
{
  //  freopen("input.txt","rt",stdin);
    int n, m;
    while (scanf("%d%d", &n, &m)) {
        if (!n && !m) break;
        vector<int> toNode[30];       // toNode[i]儲存i_node能走向哪幾個點
        for (int i=0, n1, n2; i<m; ++i) {
            scanf("%d%d", &n1, &n2);
            toNode[n1].push_back(n2);
            toNode[n2].push_back(n1);
        }
        bool visit[30][30] = {0};     //visit[i][j]=1 表示i_j這條線已經走過
        int longest = 0;
        for (int i=0; i<n; ++i){
            int length = DFS(i, toNode, 0, visit);
            if (length > longest)
                longest = length;
        }
        printf("%d\n", longest);
    }
}