POJ 3310 Caterpillar
問題
無向グラフが与えられる。
グラフがキャタピラであるかを判定せよ。
ただしグラフがキャタピラであるとは、
グラフ上にあるパスが存在し、グラフの任意の点からのそのパスへの最短距離が1以下であることを言う。
制約条件
グラフの頂点数≦100
グラフの辺≦300
与えられるグラフにループはない
方針
与えられるグラフにループはないので、グラフは(連結ならば)木となる。
キャタピラのパスはグラフの最遠点対をとればよい。
そのパス上およびパスに隣接する頂点を塗りつぶし、塗られていない点があったらキャタピラではなく、なかったらキャタピラである。
ソースコード
int prev[100]; bool ok[100]; int n,e,s,t,mx,far; vector<vi> G; void dfs(int c,int d){ if(d>mx){ mx=d; far=c; } rep(i,G[c].size())if(prev[G[c][i]]<0){ prev[G[c][i]]=c; dfs(G[c][i],d+1); } } bool solve(){ G.clear(); G.resize(n); rep(i,e){ int a,b; scanf("%d%d",&a,&b); a--; b--; G[a].pb(b); G[b].pb(a); } if(e!=n-1)return 0; mx=0; rep(i,n)prev[i]=-1; prev[0]=0; dfs(0,0); s=far; mx=0; rep(i,n)prev[i]=-1; prev[s]=s; dfs(s,0); t=far; ok[t]=1; rep(i,n)ok[i]=0; for(int i=t;;i=prev[i]){ rep(j,G[i].size())ok[G[i][j]]=1; if(i==s)break; } rep(i,n)if(!ok[i])return 0; return 1; } int main(){ int cs=0; while(scanf("%d",&n),n){ scanf("%d",&e); printf("Graph %d is ",++cs); if(!solve())printf("not "); puts("a caterpillar."); } return 0; }