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; }