PKU 3310 Caterpillar

http://poj.org/problem?id=3310
無向グラフがあたえられる。
ここで無向グラフが木になっており、あるノードからあるノードを結ぶパスの上から、パスの上のノードの隣に全てのノードを含む時、そのパスをcaterpillarを呼ぶ?
この無向グラフがcaterpillarを含んでいるかを判定しろというような問題。

連結性とサイクルがないことを確認したあと、パスを全生成して条件を満たすものがあるかどうかを調べる。

これもまた読み返したくないソースコード。

int un[100];
int find(int x){
  if(un[x]==x)return x;
  return un[x]=find(un[x]);
}

void unit(int a,int b){
  un[find(a)]=un[find(b)]=find(a);
}

vector<int>G[100];
bool vis[100];
bool onpath[100];

bool path(int u,int t){
  vis[u]=true;
  if(u==t){
    onpath[u]=true;
    return true;
  }
  rep(i,SZ(G[u])){
    if(vis[G[u][i]])continue;
    if(path(G[u][i],t))return onpath[u]=true;
  }
  return false;
}

main(){
  int n;
  int gr=0;
  while(cin>>n,n){
    printf("Graph %d is ",++gr);
    rep(i,n){
      un[i]=i;
      G[i].clear();
    }
    bool ok=true;
    int e;
    cin>>e;
    rep(i,e){
      int a,b;
      cin>>a>>b;
      --a,--b;
      if(find(a)==find(b))ok=false;
      unit(a,b);
      G[a].pb(b);
      G[b].pb(a);
    }
    rep(i,n)ok&=find(0)==find(i);

    if(!ok){
      puts("not a caterpillar.");
      continue;
    }

    ok=false;
    rep(i,n){
      rep(j,i){
        memset(vis,0,sizeof(vis));
        memset(onpath,0,sizeof(onpath));
        path(i,j);
        bool tok=true;
        rep(k,n){
          if(onpath[k])continue;
          bool ttok=false;
          rep(l,SZ(G[k])){
            if(onpath[G[k][l]]){
              ttok=true;
              break;
            }
          }
          if(!ttok){
            tok=false;
            break;
          }
        }
        if(tok){
          ok=true;
          break;
        }
      }
      if(ok)break;
    }
    if(!ok)cout<<"not ";
    cout<<"a caterpillar."<<endl;
  }
}