3310 Caterpillar
http://acm.pku.edu.cn/JudgeOnline/problem?id=3310
图的操作，题目的意思是：
给你一个图，判断它是不是caterpillar
是caterpillar的条件是：
1.首先这个图不能有环
2.最重要的是，这个图中可以找到一条路径
这条路径的一定可以经过图中所有点，或邻居点
和ZGG讨论之前我建立起我的思路：
1.首先为了防止过多的遍历，我用的是邻接表来实现
2.图是无向的，于是我把点a,b双向都标记上
3.去掉所有度为一的点，重点建立起一个图这个图里面的点为mainpoint
4.然后操作这些点，这样对这些剩下的点有这么几种情况
a,如果有某个点的度为0，那么这个图不是 caterpillar
b,如果图有大于两个的点度为一，那么这个图，有多条路不是caterpillar
c,如果图有小于两个的点度为一，那么这个图有环，不是caterpillar
d,还有最后一种就是只有两个点度为一，其它的点度为二，那么这个图是caterpillar
AC CODE:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int g[102][102]; // store the resoures points
int newg[102][4]; // store the main points
int used[102]; //
bool mainpoint[102];
int main()
{
int i,j,k,n,m,t,e,a,b;
int cnt = 0;
while (scanf("%d",&n)!=EOF,n)
{
int top = 0;
cnt++;
scanf("%d",&e);
memset(g,0,sizeof(g));
memset(newg,0,sizeof(newg));
memset(used,0,sizeof(used));
memset(mainpoint,0,sizeof(mainpoint));
for (i=0;i<=n;i++)
{
g[i][0] = 1;
newg[i][0] = 1;
}
for (i=0;i<e;i++)
{
scanf("%d %d",&a,&b);
g[a][g[a][0]++] = b;
g[b][g[b][0]++] = a;
}
/*
for (i=1;i<=n;i++)
{
for (j=1;j<g[i][0];j++)
printf("%d ",g[i][j]);
printf("/n");
}
*/
//find the board point
// printf("------------------/n");
for (i=1;i<=n;i++)
{
if (used[i]) continue;
if (g[i][0] == 2) //find the leg
{
used[i] = 1;
}
else if (g[i][0] == 1) break; //if a point is alone then break;
else // these are the main points
{
//delete the legs renew the map
for (j=1;j<g[i][0];j++) // search all the points of one main points
{
int point = g[i][j];
if (!used[point])
{
if (g[point][0] == 2) // if the point is board that to say it is not a main point
used[point] = 1;
else if (g[point][0] == 1) //it is alone
break;
else // the point is main point
{
mainpoint[i] = 1;
mainpoint[point] = 1;
for (k = 1;k<newg[i][0] ;k++)
{
if (newg[i][k] == point)
break;
}
if (k != newg[i][0])
continue;
newg[i][newg[i][0]++] = point;
newg[point][newg[point][0]++] = i;
if (newg[i][0]>=4 || newg[point][0]>=4 ) break; //there are more than two roads on this point
}
}
}
if (j != g[i][0])
break;
}
}
if (i!=n+1)
{
printf("Graph %d is not a caterpillar./n",cnt);
continue;
}
int counter = 0;
for (i=1;i<=n;i++)
{
if (!mainpoint[i]) continue;
if (newg[i][0] == 1) break;
else if (newg[i][0] == 2) counter++;
if (counter > 2) break;
}
if (i!=n+1 || counter!=2)
{
printf("Graph %d is not a caterpillar./n",cnt);
}
else
printf("Graph %d is a caterpillar./n",cnt);
}
return 0;
}