题目链接：http://poj.org/problem?id=3310
思路：首先是判断图的连通性，以及是否有环存在，这里我们可以用并查集判断，然后就是找2次dfs找树上最长直径了，并且对树上最长直径上的点进行标记，于是根据题意我们可以发现，如果这个图是“caterpillar”的话，那么他所有的边要么两端都在树上最长直径上，要么就是其中一端在，于是我们可以再次dfs进行判断就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111 struct Edge{
int v,next;
}edge[MAXN*MAXN]; int n,m,NE;
int head[MAXN]; void Insert(int u,int v)
{
edge[NE].v=v;
edge[NE].next=head[u];
head[u]=NE++;
} int parent[MAXN]; void Initiate()
{
for(int i=;i<=n;i++){
parent[i]=i;
}
} int Find(int x)
{
if(x==parent[x]){
return parent[x];
}
parent[x]=Find(parent[x]);
return parent[x];
} bool Judge()
{
int cnt=;
for(int i=;i<=n;i++){
if(parent[Find(i)]==i)cnt++;
}
return cnt==;
} int dep[MAXN];
int path[MAXN];
bool mark[MAXN],vis[MAXN]; void dfs_dep(int u,int father)
{
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(v==father)continue;
dep[v]=dep[u]+;
path[v]=u;
dfs_dep(v,u);
}
} bool dfs(int u)
{
vis[u]=true;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(vis[v])continue;
if(mark[u]||mark[v]){
if(dfs(v))return true;
}
return false;
}
return true;
} int main()
{
// freopen("1.txt","r",stdin);
int u,v,st,ed,tmp,t=;
while(~scanf("%d",&n)&&n){
scanf("%d",&m);
NE=;
memset(head,-,sizeof(head));
Initiate();
bool flag=true;
while(m--){
scanf("%d %d",&u,&v);
Insert(u,v);
Insert(v,u);
if(Find(u)!=Find(v))parent[Find(u)]=Find(v);
else flag=false;
}
if(!flag||!Judge()){
printf("Graph %d is not a caterpillar.\n",t++);
continue;
}
dep[]=;
dfs_dep(,-);
ed=;
for(int i=;i<=n;i++){
if(dep[i]>dep[ed])ed=i;
}
dep[st=ed]=;
dfs_dep(st,-);
ed=;
for(int i=;i<=n;i++){
if(dep[i]>dep[ed])ed=i;
}
memset(mark,false,sizeof(mark));
path[st]=-;
mark[st]=true;
tmp=ed;
while(path[tmp]!=-){
mark[tmp]=true;
tmp=path[tmp];
}
memset(vis,false,sizeof(vis));
if(dfs()){
printf("Graph %d is a caterpillar.\n",t++);
}else
printf("Graph %d is not a caterpillar.\n",t++);
}
return ;
}