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; 
} 
 

补充：软件开发 , C++ ,

上一个：URAL 1136 Parliament 二叉树水题 BST后序遍历建树
下一个：hdu 2824 The Euler function（欧拉函数）