PKU 3895 Cycles of Lanes
http://poj.org/problem?id=3895
グラフが与えられるのでサイクルのうち最長のものの長さを求めろというような問題。
おのおのノードはたかだか一つのサイクルにしか属さないとしてよい。
行って戻ってというので2を数えてしまって1WA
単純なdfsで行けました
int vis[10000]; vector<int> G[10000]; int ans; void dfs(int v,int de){ if(vis[v]!=-1 && vis[v]+2==de)return; if(vis[v]!=-1){ ans=max(ans,de-vis[v]); return; } vis[v]=de; FOR(it,G[v]) dfs(*it,de+1); } void solve(){ int n,m; cin>>n>>m; rep(i,n)G[i].clear(); rep(i,m){ int a,b; cin>>a>>b; --a,--b; G[a].pb(b); G[b].pb(a); } memset(vis,-1,sizeof(vis)); ans=0; dfs(0,0); cout<<ans<<endl; } main(){ int t; cin>>t; while(t--) solve(); }