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