果搜即可。
从一个起点开始出发，尝试每条没有走过的边，直到不能走为止。
注意到和顶点数相比，边数要少得多，所以使用邻接表存储。
以下是我的代码：
#include<list>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(27);
int n,m,ans;
list<int> g[kMaxn];
bool used[kMaxn][kMaxn];
void dfs(int node,int length)
{
if(ans<length)
ans=length;
for(list<int>::iterator i=g[node].begin();i!=g[node].end();i++)
if(!used[node][*i])
{
used[node][*i]=used[*i][node]=true;
dfs(*i,length+1);
used[node][*i]=used[*i][node]=false;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
while(scanf("%d%d",&n,&m)==2 && (n || m))
{
for(int i=0;i<n;i++)
g[i].clear();
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
ans=0;
for(int i=0;i<n;i++)
{
memset(used,false,kMaxn*kMaxn*sizeof(bool));
dfs(i,0);
}
printf("%d\n",ans);
}
return 0;
}
posted on 2011-04-20 10:39
lee1r 阅读(267)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索