UVa 539 & POJ 2258 - The Settlers of Catan

傳送門UVa 539  & POJ 2258 - The Settlers of Catan

題意是統計圖中最長路，可以有斷點。

比較基礎的回溯題，不過第一次寫的時候我把vis隻開了一維，這樣的話往前走就回不來了，WA。

還是沒有對前面的内容了解好啊，還要多做題。。

BTW，UVa太靠不住了，已經挂了兩天了（╯‵□′）╯  ┴─┴ 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int vis[30][30], G[30][30], longest, n;

void DFS(int curLong, int cur);

int main()
{
    //freopen("input.txt", "r", stdin);
    int m, i, j, a, b;
    while (scanf("%d%d", &n, &m), m + n)
    {
        longest = 0;
        memset(vis, 0, sizeof(vis));
        memset(G, 0, sizeof(G));
        for (i = 0; i < m; i++)
        {
            scanf("%d%d", &a, &b);
            G[a][b] = G[b][a] = 1;
        }
        for (i = 0; i < n; i++) //因為可能有斷點，是以要周遊每個點。
            DFS(0, i);
        printf("%d\n", longest);
    }
    return 0;
}

void DFS(int curLong, int cur)
{
    longest = max(curLong, longest);
    for (int i = 0; i < n; i++)
        if (!vis[cur][i] && G[cur][i])
        {
            vis[cur][i] = vis[i][cur] = 1;
            DFS(curLong + 1, i);
            vis[cur][i] = vis[i][cur] = 0;
        }
}