UVA 539 The Settlers of Catan dfs找最長鏈

題意：畫邊求最長鏈，邊不能重復數點可以。

很水，用暴力的dfs即可，因為數據不大。

本來以為可以用floyd進行dp的，後來想想好像不能在有回路上的圖跑。。。於是沒去做。

#include <cstdio>  
const int maxn = 30; 
 
int e[maxn][maxn]; 
int vis[maxn][maxn]; 
int n, m, max; 
 
void dfs(int x, int d) { 
    if (max < d) 
        max = d; 
    for (int i = 0; i < n; i++) 
        if (!vis[x][i] && e[x][i]) { 
            vis[x][i] = vis[i][x] = 1; 
            dfs(i, d + 1); 
            vis[x][i] = vis[i][x] = 0; 
        } 
} 
 
int main() { 
    while (scanf("%d%d", &n, &m) && n && m) { 
        max = 0; 
        int a, b; 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                vis[i][j] = e[i][j] = 0; 
        for (int i = 0; i < m; i++) { 
            scanf("%d%d", &a, &b); 
            e[a][b] = e[b][a] = 1; 
        } 
        for (int i = 0; i < m; i++) 
            dfs(i, 0); 
        printf("%d\n", max); 
    }//while  
    return 0; 
}