果搜即可。
從一個起點開始出發，嘗試每條沒有走過的邊，直到不能走為止。
注意到和頂點數相比，邊數要少得多，所以使用鄰接表存儲。
以下是我的代碼：
#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 閱讀(288)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索