北方的路--奶牛马拉松--毛虫图

一）POJ2631 北方的路
Building and maintaining roads among munities in the far North is an expensive business With this in mind, the roads are build such that there is real_src ="http://blog.sina.com.cn/s/poj/images/3310_1gif" BORDER="0" ALT="北方的路--奶牛马拉松--毛虫图" TITLE="北方的路--奶牛马拉松--毛虫图" />

Input
There will be multiple test cases Each test case starts with a line containing n indicating the number of nodes, numbered 1 through n (a value of n评 = 0 indicates end-of-input) The next line will contain an integer e indicating the number of edges Starting>一个无向图，如果这个无向图上有一条路径能将所有的度数大于等于2的节点串联起来，而且这个无向图没有环而且是连通的，就
输出Graph 2 is a caterpillar
否则输出Graph 1 is not a caterpillar。

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=1;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 t=0;
for(int i=1;i<=n;i )
if(parent[Find(i)]==i) t ;
return t==1;
} int dep[MAXN];
int path[MAXN];
bool mark[MAXN],vis[MAXN]; void dfs_dep(int u,int father)
{
for(int i=head[u];i!=-1;i=edge[i]next){
int v=edge[i]v;
if(v==father)continue;
dep[v]=dep[u] 1;
path[v]=u;
dfs_dep(v,u);
}
} bool dfs(int u)
{
vis[u]=true;
for(int i=head[u];i!=-1;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()
{
int u,v,st,ed,tmp,t=1;
while(~scanf("%d",&n)&&n){
scanf("%d",&m);
NE=0;
memset(head,-1,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[1]=0;
dfs_dep(1,-1);
ed=1;
for(int i=1;i<=n;i ){
if(dep[i] > dep[ed])ed=i;
}
dep[st=ed]=0;
dfs_dep(st,-1);
ed=1;
for(int i=1;i<=n;i ){
if(dep[i] > dep[ed])ed=i;
}
memset(mark,false,sizeof(mark));
path[st]=-1;
mark[st]=true;
tmp=ed;
while(path[tmp]!=-1){
mark[tmp]=true;
tmp=path[tmp];
}
memset(vis,false,sizeof(vis));
if(dfs(1)){
printf("Graph %d is a caterpillar\n",t );
}else
printf("Graph %d is not a caterpillar\n",t );
}
return 0;
}