題意：判斷一個(gè)給定的圖，沒有環(huán)，而且存在一個(gè)鏈，圖上的所有點(diǎn)或者在這條鏈上或者在其的鄰居
題解：
1.判斷環(huán)：
對(duì)于無向圖：如果 點(diǎn) < 邊 + 1，則存在環(huán)；
然后使用并查集進(jìn)一步判斷環(huán)的存在

2.判斷是否存在鏈
首先統(tǒng)計(jì)各個(gè)點(diǎn)的度，然后對(duì)于度為1的點(diǎn)，將其相連的邊刪掉，再統(tǒng)計(jì)新圖的度，這時(shí)新圖應(yīng)該剩下一條鏈，
也就是說，新圖的不存在大于2個(gè)度為1的點(diǎn)，而且這個(gè)點(diǎn)在舊圖的度是大于1的。

代碼：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int N = 105;

vector<int> graphs[N];
int deg[N];
int degOld[N];
int n,e;
int cnt;

class UnionSet
{
private:
    int parent[N];
    int rank[N];
    int size;
public:
    UnionSet()
    {
        size = 0;
    }

    UnionSet(int _size)
    {
        init(_size);
    }
    ~UnionSet()
    {

    }

    void init(int _size)
    {
        size = _size;
        for (int i = 0; i < size; ++i)
        {
            parent[i] = -1;
            rank[i] = 1;
        }
    }

    void adjust(int _root,int _x)
    {
        int i = _x;
        int j ;
        while(parent[i] >= 0)
        {
            j = parent[i];
            parent[i] = _root;
            i = j;
        }
    }

    int getRoot(int _x)
    {
        int r = _x;
        while(parent[r] >= 0)
        {
            r= parent[r];
        }

        //adjust
        adjust(r,_x);
        return r;

    }

    void join(int _r1,int _r2)
    {
        if (_r1 == _r2)
        {
            return ;
        }
        int root1 = getRoot(_r1);
        int root2 = getRoot(_r2);
        if (root1 == root2)
        {
            return ;
        }
        if (rank[root1] > rank[root2])
        {
            parent[root2] = root1;
            rank[root1] += rank[root2];
        }
        else
        {
            parent[root1] = root2;
            rank[root2] += rank[root1];
        }

    }

    int getRank(int _x)
    {
        return rank[_x];
    }

};

static UnionSet uSet;



void Test()
{
    memset(deg,0,sizeof(deg));
    for (int i = 0; i < N; ++i)
    {
        graphs[i].clear();
    }
    int a,b;
    uSet.init(n+1);
    for (int i = 0; i < e; ++i)
    {
        scanf("%d %d",&a,&b);
        deg[a]++;
        deg[b]++;
        graphs[a].push_back(b);
        graphs[b].push_back(a);
        uSet.join(a,b);
    }
    if (n < e + 1)
    {
        printf("Graph %d is not a caterpillar.\n", cnt);
        return ;
    }
    for (int i = 2; i <= n; ++i)
    {
        if (uSet.getRoot(1) != uSet.getRoot(i))
        {
            printf("Graph %d is not a caterpillar.\n", cnt);
            return ;
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        degOld[i] = deg[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        if (degOld[i] == 1)
        {
            for (int j = 0; j < graphs[i].size(); ++j)
            {
                deg[graphs[i][j]]--;
            }
        }
    }

    int tmp = 0;
    for (int i = 1; i <= n; ++i)
    {
        if(degOld[i] > 1 && deg[i] == 1)
            ++tmp;
    }
    if(tmp > 2)
        printf("Graph %d is not a caterpillar.\n", cnt);
    else
        printf("Graph %d is a caterpillar.\n", cnt);

}

int main()
{
    //freopen("data.txt","r",stdin);
    cnt = 0;
    while(scanf("%d",&n) != EOF)
    {
        if(n == 0)
            break;
        scanf("%d",&e);
        ++cnt;

        Test();
    }
    return 0;
}