AOJ 0508: String With Rings

"嘘枝刈り"+DFS
適当に次数の小さいものを採用するようにしたら、何故か通りました。

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;


int v[100];
vector<int> g[100];

inline int dfs(int x){
	int ans = 0;
	for(int i = 0,l = g[x].size(); i < l; i++){
		int y = g[x][i];
		v[x]++;
		if(!v[y]){
			ans = max(ans,dfs(y)+1);
		}
		v[x]--;
	}
	return ans;
}

int main(){
	int n;
	while(scanf("%d",&n),n){
		int M = 0;
		for(int i = 0; i < n; i++){
			int a,b;
			scanf("%d%d",&a,&b);
			M = max(M,b);
			a--;b--;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		
		int ans = 0,size = 100;//sizeは嘘枝刈り用
		
		for(int i = 0; i < M; i++){
			size = min((int)g[i].size(),size);
		}
		size += 3;//2だとWAすることを確認済み
		
		for(int i = 0; i < M; i++){
			if(g[i].size()<=size)ans = max(ans,dfs(i)+1);
		}
		
		printf("%d\n",ans);
		
		for(int i = 0; i < M; i++){
			g[i].clear();
		}
	}
	return 0;
}