題干：

An undirected graph is called a caterpillar if it is connected, has no cycles, and there is a path in the graph where every node is either on this path or a neighbor of a node on the path. This path is called the spine of the caterpillar and the spine may not be unique. You are simply going to check graphs to see if they are caterpillars.

For example, the left graph below is not a caterpillar, but the right graph is. One possible spine is
shown by dots.

?

?

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 on the following line will be?e?pairs?n1?n2indicating an undirected edge between nodes?n1?and?n1. This information may span multiple lines. You may assume that?n?≤ 100 and?e?≤ 300. Do not assume that the graphs in the test cases are connected or acyclic.

Output

For each test case generate one line of output. This line should either be

????Graph?g?is a caterpillar.?
or?
????Graph?g?is not a caterpillar.?

as appropriate, where?g?is the number of the graph, starting at 1.

Sample Input

22 21 1 2 2 3 2 4 2 5 2 6 6 7 6 10 10 8 9 10 10 12 11 12 12 13 12 17 18 17 15 17 15 14 16 15 17 20 20 21 20 22 20 19 16 15 1 2 2 3 5 2 4 2 2 6 6 7 6 8 6 9 9 10 10 12 10 11 10 14 10 13 13 16 13 15 0

Sample Output

Graph 1 is not a caterpillar. Graph 2 is a caterpillar.

題目大意：

? ??判斷一個圖是否滿足下列條件：

? ? ? ? ? ? 1.是一棵樹（是否全部連通并且不存在環）。

? ? ? ? ? ? 2.存在一條脊椎（主鏈），使得所有點要么在鏈上要么與鏈上的點距離為1（即支鏈不會再有支鏈）。?
? ? 輸入格式，多組輸入數據，每一組，第一行個數n，第二行邊數m，第三行共m對（2*m個），每一對的數字是點的編號，表示這兩個點之間連一條邊。?

解題報告：

? ? ?這題做法很多？最近在學樹的直徑所以用此法解題。其實這里的dfs就是一層的遞歸啦沒這么高大上。。。判斷支鏈有無支鏈而已。

AC代碼：（代碼有點長哦但是各函數分工還是比較明確的）

#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; int n,m; int cnt; int head[1000 + 5]; int f[1000 + 5]; bool vis[1000 + 5]; struct Edge {int pos,to;int w;//此題中就是零，，沒意義int ne; } e[1000 + 5]; struct Point {int pos;int s;Point(){}Point(int pos,int s):pos(pos),s(s){} }; //記錄路徑 int rem[505]; void add(int u,int v,int w) {e[cnt].pos = u;e[cnt].to = v;e[cnt].w = w;e[cnt].ne = head[u];head[u] = cnt++; } void init() {cnt = 0;memset(head ,-1, sizeof(head));memset(vis,0,sizeof(vis));for(int i = 1; i<=n; i++) f[i] = i; } int getf(int v) {return f[v] == v? v:f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u);int t2 = getf(v);f[t2] = t1; } //判斷連通無環 bool judge() {if(m != n-1) return false;for(int i = 1; i<=n; i++) {if(getf(i) != getf(1) ) {return false;}}return true; } int bfs(int st) {queue<Point> q;q.push(Point(st,1));int retp = st;int maxx = 0;vis[st] = 1;while(q.size()) {Point cur = q.front();q.pop();for(int i = head[cur.pos]; i!=-1; i = e[i].ne) {Point now = Point(e[i].to, cur.s +1);if(vis[now.pos] == 1) continue;vis[now.pos] = 1;rem[now.pos] = cur.pos;q.push(now);if(now.s>maxx) {maxx = now.s;retp = now.pos;}}}return retp; } int dfs(int st) { // printf(":::::::::::::::::::::::::::\n");int cnt = 0;for(int i = head[st];i!=-1;i=e[i].ne) {if(vis[e[i].to] == 0) {vis[e[i].to] = 1; cnt+=dfs(e[i].to)+1;}} // printf("cnt = %d\n",cnt);return cnt; } int main() {int a,b,iCase = 0;while(scanf("%d",&n) ) {if(n == 0) break;scanf("%d",&m);init();for(int i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b,0);add(b,a,0);//注意 需要加兩條邊！ merge(a,b);}if(!judge()) {printf("Graph %d is not a caterpillar.\n",++iCase);continue;}int u = bfs(1);//樹的直徑的一個端點 memset(vis,0,sizeof(vis));memset(rem,0,sizeof(rem));int v = bfs(u); // printf("%d %d\n",u,v);//必須從v開始倒著找，不能u開始！ // printf("%d ",v);//將骨架上的點標記為走過。 memset(vis,0,sizeof(vis) );vis[v] = 1;int flag = 0; // printf(":::::::::::::::::::::::::::\n");for(int i = v; rem[i]!=0; i=rem[i]) vis[i] = 1;if(dfs(v)>1) {flag = 1;printf("Graph %d is not a caterpillar.\n",++iCase);continue;}for(int i = rem[v]; rem[i]!=0; i=rem[i]) { // vis[i] = 1;for(int j = head[i];j !=-1;j=e[j].ne) {if(vis[e[j].ne] == 1) continue;if(dfs(e[j].ne)>0) { // printf("%d ",rem[i]);flag = 1;printf("Graph %d is not a caterpillar.\n",++iCase);break;}}if(flag == 1) break; // printf("%d ",rem[i]);}if(flag == 0) {printf("Graph %d is a caterpillar.\n",++iCase);}}return 0 ; }

總結：

? ? 加邊別忘是加兩條邊，無向圖！?

總結

以上是生活随笔為你收集整理的【POJ - 3310】Caterpillar（并查集判树+树的直径求树脊椎(bfs记录路径)+dfs判支链）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。