题意：
给定一幅图， 问符不符合一下两个条件；
（1） 图中没有环
（2）图中存在一条链， 点要么在链上， 要么是链上点的邻居。
分析：
建图，记录度数， 去掉所有度为1的点， 然后看看剩下是否是有2个度为1的点和其他都是度为2的点。
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<string> #include<map> #include<stack> #include<vector> #include<algorithm> #include<cmath> #define rep(i,a,b) for(int i = a; i < b; i++) #define _rep(i,a,b) for(int i = a; i <= b; i++) using namespace std; int G[107][107]; int n, m; int deg[107], vis[107]; int main(){ // freopen("1.txt","r", stdin); int kase = 1; while(~scanf("%d", &n) && n){ memset(G,0,sizeof(G)); memset(deg,0,sizeof(deg)); memset(vis,0,sizeof(vis)); scanf("%d", &m); for(int i = 0; i < m ; i++){ int u, v; scanf("%d %d", &u, &v); G[u][v] = G[v][u] = 1; deg[u]++; deg[v]++; } for(int i = 1; i <= n; i++){ if(deg[i] == 1){ //把度为1的点全部删除， 把链上的分叉的消去 vis[i] = 1; for(int j = 1; j <= n; j++){ if(G[i][j]) deg[j]--; } } } int ok = 1, _1 = 0, _2 = 0,cnt = 0; for(int i = 1;i <= n; i++){ if(!vis[i]){ cnt++; if(deg[i] == 1) _1++;//统计剩下点度为1的 else if(deg[i] == 2) _2++;//统计剩下度为2的 } } if(!(_1 == 2 && _2 == (cnt-2))) ok = 0;//如果有2个度为1， 其他都是2， 那么就是一条链， 其他情况都不符合 if(ok) printf("Graph %d is a caterpillar. ",kase++); else printf("Graph %d is not a caterpillar. ",kase++); } return 0; }