Poj 1386歐拉回路

題意：如果單詞A的結尾字母與單詞B的首字母相同，那麼可以認為是A到B相通。給出一系列單詞，求這些詞按照某種排列能否串通。
題解：
如果直接按照題意建模，以單詞為頂點，邊表示兩兩相通，那麼將會得到哈密頓回路模型。顯然是很難解的。
換一種方式，以字母為頂點，邊表示傳送的單詞，那麼就得到歐拉回路模型的圖，可以按照歐拉定理求解。
以下給出Euler圖的相關知識：
Euler回路：G中經過每條邊一次且僅一次的回路
Euler路徑：G中經過每條邊一次且僅一次的路徑
無向圖存在Euler回路定理：當它是連通圖+頂點度數為偶數
無向圖存在Euler路徑定理：當它是連通圖+除兩個頂點度為奇數外，其余為偶數
有向圖存在Euler回路定理：當它是連通圖+頂點入度 == 出度
有向圖存在Euler路徑定理：當它是連通圖+除一個頂點的入度和出度的差的絕對值小1外，其余相等
代碼： #include <stdio.h>
#include <string.h>
const int N = 30;

class UnionSet
{
private:
    int parent[N];
    int rank[N];
    int size;
public:
    UnionSet(int _size):size(_size)
    {
        init();
    }
    ~UnionSet()
    {
    }

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

    int root(int _x)
    {
        int r = _x;
        while(parent[r] >= 0)
            r = parent[r];
        int i = _x;
        int j;
        while(parent[i] >= 0)
        {
            j = parent[i];
            parent[i] = r;
            i = j;
        }
        return r;
    }

    int Union(int _r1,int _r2)
    {
        if(_r1 == _r2)
            return _r1;
        else
        {
            int root1 = root(_r1);
            int root2 = root(_r2);
            if(root1 == root2)
                return root1;
            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];
    }
};
char buf1[1024];

void Test()
{
    int In[30] = {0};
    int Out[30] = {0};
    bool visited[30] = {false};
    UnionSet Set(28);
    int n;
    scanf("%d",&n);
    bool flag = false;
    int start = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%s",buf1);
        int len = strlen(buf1);
        Set.Union(buf1[0] - a,buf1[len-1] - a);
        In[buf1[len-1] - a]++;
        Out[buf1[0] - a]++;
        visited[buf1[0] - a] = true;
        visited[buf1[len-1] - a] = true;
        if (!flag)
        {
            start = buf1[0] - a;
            flag = true;
        }
    }
   
    for (int i = 0; i < 26; ++i)
    {
        if (i != start)
        {
            if (visited[i] && (Set.root(start) != Set.root(i)))
            {
                printf("The door cannot be opened. ");
                return;
            }
        }
    }
    int cntIn = 0;
    int cntOut = 0;
    for (int i = 0; i < 26; ++i)
    {
        if (visited[i])
        {
            if (In[i] != Out[i])
            {
                if (In[i] - Out[i] == -1)
                {
                    cntIn++;
                }
                else if (In[i] - Out[i] == 1)
                {
                    cntOut++;
                }
                else
            &nbs