地址：http://acm.hit.edu.cn/judge/show.php?Proid=1033&Contestid=0
思路：可以把這道題等價地看成有向圖中求哈密頓路的問題，每個在單詞首尾出現過的字母看作一個節點，每個單詞首字母看作節點的出度加1，尾字母看作節點的入度加1，而形成哈密頓路的條件是除了哈密頓路首尾兩個節點外，其他節點的出度等于入度，而首節點出度比入度多1，尾節點入度比出度多1。除此之外，還要考慮圖的連通性問題，因為不連通的圖是無法形成哈密頓路的，使用并查集來判斷圖是否連通。并查集的內容詳情可見：http://www.shnenglu.com/amazon/archive/2009/08/15/93457.html
代碼如下：

#include <stdio.h>
#include <string.h>
#include <memory.h>

#define OUT 10

typedef struct  
{
    int parent;
    int height;
}Node;

Node set[26];
bool visited[26];
int record[26], num_record;

void Init()
{
    int i;

    for(i = 0; i < 26; i++)
    {
        visited[i] = false;
        set[i].parent = i;
        set[i].height = 1;
    }
    num_record = 0;
}

int Find(int x)
{
    while(x != set[x].parent)
    {
        x = set[x].parent;
    }

    return x;
}

void Merge(int x, int y)
{
    if(x == y)
    {
        return;
    }
    if(set[x].height == set[y].height)
    {
        set[y].parent = x;
        set[x].height++;
    }
    else if(set[x].height > set[y].height)
        set[y].parent = x;
    else
        set[x].parent = y;
}

int main()
{
    int T, N;
    int i, j;
    char word[1005];
    int letter[26];
    int front, behind;
    int a, b;
    bool flag;

    scanf("%d", &T);

    for(i = 0; i < T; i++)
    {
        front = behind = 0;
        memset(letter, 0, sizeof(letter));
        Init();

        scanf("%d", &N);

        for(j = 0; j < N; j++)
        {
            scanf("%s", word);
            a = word[0] - 'a';
            b = word[strlen(word) - 1] - 'a';
            letter[a]++;
            letter[b]--;
            Merge(Find(a), Find(b));
            if(visited[a] == false)
            {
                visited[a] = true;
                record[num_record++] = a;
            }
            if(visited[b] == false)
            {
                visited[b] = true;
                record[num_record++] = b;
            }

        }

        flag = false;
        a = Find(record[0]);
        for(j = 1; j < num_record; j++)
        {
            if(a != Find(record[j]))
            {
                flag = true;
                break;
            }
        }
        if(flag == true)
        {
            printf("The door cannot be opened.\n");
            continue;
        }
        
        for(j = 0; j < 26; j++)
        {
            if(letter[j] > 1 || letter[j] < -1)
            {
                front = behind = OUT;
                break;
            }
            else if(letter[j] == 1)
                front++;
            else if(letter[j] == -1)
                behind++;
        }

        if((front == 1 && behind == 1) || (front == 0 && behind == 0))
        {
            printf("Ordering is possible.\n");
        }
        else
        {
            printf("The door cannot be opened.\n");
        }
    }

    return 0;
}