uva539 卡坦岛简单回溯！

开始想复杂了，用了好多数组判断节点的度、边是否已经走过，结果导致超时了，后来简化成如下版本，走过的标志不需要另辟vis数组，只要将map【i】【j】和map【j】【i】赋值0即可。

#include<iostream>  
#include<cstring>  
  
using namespace std;  
  
int n,m,Max,map[30][30];  
  
void dfs(int node,int path)     //node：当前节点，path:当前路径长度  
{  
    int i;  
    if (path>Max) Max=path;  
    for (i=0;i<n;i++)  
    {  
        if (map[node][i])  
        {  
            map[node][i]=map[i][node]=0;  
            dfs(i,path+1);  
            map[node][i]=map[i][node]=1;  
        }  
    }  
}  
int main()  
{  
    while(cin>>n>>m&&n)  
    {  
        memset(map,0,sizeof(map));  
        for (int i=0;i<m;i++)  
        {  
            int a,b;  
            cin>>a>>b;  
            map[a][b]=map[b][a]=1;  //因是无向图，所以矩阵应为对称阵  
        }  
        Max=0;  
        for (int i=0;i<n;i++)  
            dfs(i,0);               //依次以各节点作为链的起始点  
        cout<<Max<<endl;  
    }  
}

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

uva539 卡坦岛 简单回溯！

uva539 卡坦岛简单回溯！