AOJ : 0508 - String With Rings

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0508
日本語の問題文なので省略です

アルゴリズム

各リングをノード、紐をエッジとみなして、グラフを作成します。
そのグラフにおいて、「同じノード・エッジを1度しか通らない」ような最長経路を見つけるのが、この問題です。

この問題を解くためには、「深さ優先探索」を行います。
グラフ上のあるノードを始点として、その点から深さ優先探索を行い最長経路を見つけます。
これを全てのノードに対して行います。

ただし、単純にこの作業を行う場合、TLEを起こしてしまうこともあるため、次の性質を思いついて、プログラムを少し工夫しました。

ある「連結」なグラフにおいて、「同じノード・エッジを1度しか通らない」ような最長経路がある。この経路の始点or終点は、必ずグラフ上の最小次数のノードのどれかになる。

プログラム

#include <stdio.h>
#include <string.h>

#define REP(i,n,m) for(i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int t[101][101];
int size[101];
int notEnd[101];
int used[101];

int solve(int idx,int s){
	int i,tmp,res=0;

	notEnd[idx] = 0;
	used[idx] = 1;

	rep(i,size[idx]){
		if(!used[t[idx][i]]){
			tmp = solve(t[idx][i],s);
			if(res < tmp) res = tmp;
		}
	}
	used[idx] = 0;

	return res+1;
}

int main(void){
	int i,j;
	int n,from,to;
	int max,breakFlg,tmp;

	while(scanf("%d",&n) && n){
		memset(t,0,sizeof(t));
		memset(size,0,sizeof(size));
		memset(notEnd,0,sizeof(notEnd));

		rep(i,n){
			scanf("%d%d",&from,&to);
			t[from][size[from]++] = to;
			t[to][size[to]++] = from;
			notEnd[from] = notEnd[to] = 1;
		}

		max = 0;
		memset(used,0,sizeof(used));

		for(j=1;;j++){
			REP(i,1,101){
				if(size[i] == j){
					tmp = solve(i,j);
					if(max < tmp) max = tmp;
				}
			}

			breakFlg = 1;
			REP(i,1,101){
				if(notEnd[i]){
					breakFlg = 0;
					break;
				}
			}
			if(breakFlg) break;
		}

		printf("%d\n",max);
	}

	return 0;
}