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