思路
- 所谓的毛毛虫必须是树,建立图,并查集查是否有环,有则
continue
;
- 从一点出发,bfs求其到其他点距离,若有达不到的点,
continue
;
- 求出从一点出发的最远的点,再次bfs求其到其他点距离;
- 求出最远的点,即树的直径的两个端点都已经得出,回溯法标记其路径当中的每一个点;
- 标记的每一个点距离为一的点,同样标记;
- 若每一个点都被标记过,则为毛毛虫。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<string>
using namespace std;
// for(i=1;i<=t;i++)
// scanf("%d%d%d",&v,&r,&c);
// printf("%d",maxx);
int mapp[110][110],dis[110],flag[110];
int tree[110];
int root(int jie)
{
if(tree[jie]==jie)
return jie;
else
return tree[jie]=root(tree[jie]);
}
int main()
{
int i,j,k,n,e,temp,key,ccc=0,maxx;
while(1)
{
ccc++;
scanf("%d",&n);
if(n==0) break;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
mapp[i][j]=0;
memset(dis,0,sizeof(dis));
memset(flag,0,sizeof(flag));
scanf("%d",&e);
key=0;
for(i=1;i<=n;i++)
tree[i]=i;
for(i=1;i<=e;i++)
{
scanf("%d%d",&j,&k);
mapp[j][k]=1;
mapp[k][j]=1;
j=root(j);
k=root(k);
if(j!=k)
{
tree[j]=k;
}
else
{
key=1;
}
}
if(key==1)
{
printf("Graph %d is not a caterpillar.
",ccc);
continue;
}
queue<int>q;
flag[1]=1;
dis[1]=1;
q.push(1);
while(q.empty()!=true)
{
temp=q.front();
q.pop();
for(i=1;i<=n;i++)
{
if(flag[i]==0&&mapp[temp][i]==1)
{
dis[i]=dis[temp]+1;
q.push(i);
flag[i]=1;
}
}
}
maxx=0;
for(i=1;i<=n;i++)
{
if(dis[i]==0)
key=1;
if(dis[i]>maxx)
{
maxx=dis[i];
temp=i;
}
}
if(key==1)
{
printf("Graph %d is not a caterpillar.
",ccc);
continue;
}
memset(dis,0,sizeof(dis));
memset(flag,0,sizeof(flag));
flag[temp]=1;
dis[temp]=1;
q.push(temp);
while(q.empty()!=true)
{
temp=q.front();
q.pop();
for(i=1;i<=n;i++)
{
if(flag[i]==0&&mapp[temp][i]==1)
{
dis[i]=dis[temp]+1;
q.push(i);
flag[i]=1;
}
}
}
maxx=0;
for(i=1;i<=n;i++)
{
if(dis[i]>maxx)
{
maxx=dis[i];
temp=i;
}
}
memset(flag,0,sizeof(flag));
flag[temp]=1;
q.push(temp);
while(q.empty()!=true)
{
temp=q.front();
q.pop();
for(i=1;i<=n;i++)
{
if(flag[i]==0&&mapp[temp][i]==1)
{
if(dis[i]==dis[temp]-1)
{
q.push(i);
flag[i]=1;
}
}
}
dis[temp]=0;
}
for(i=1;i<=n;i++)
{
if(dis[i]==0)
{
q.push(i);
}
}
while(q.empty()!=true)
{
temp=q.front();
q.pop();
for(i=1;i<=n;i++)
{
if(mapp[temp][i]==1)
{
dis[i]=0;
}
}
}
key=0;
for(i=1;i<=n;i++)
{
if(dis[i]!=0)
{
key=1;
}
}
if(key==1)
{
printf("Graph %d is not a caterpillar.
",ccc);
}
else
{
printf("Graph %d is a caterpillar.
",ccc);
}
}
return 0;
}
来源