poj 1386 Play on Words门上的单词【欧拉回路&&并查集】

题目链接：http://poj.org/problem?id=1386

题目大意：给你若干个字符串，一个单词的尾部和一个单词的头部相同那么这两个单词就可以相连，判断给出的n个单词是否能够一个接着一个全部连通。

解题思路：其实就是让你判断是否是欧拉回路或欧拉通路，建图需要一点思维，把26个字母当成是节点，每个单词当成是一条有向边。

这题自己先实现了一遍，发现虽然样例能过，但是有些情况没有考虑到，然后看了一下别人的代码，发现大部分人都是用并查集来做的，很巧妙的做法。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

char word[1001];
int father[27], out[27], in[27], vis[30];

int find_(int x)
{
    if (father[x] != x)
        father[x] = find_(father[x]);
    return father[x];
}

void mergee(int a, int b)
{
    if (find_(a) != find_(b))
        father[find_(a)] = find_(b);
}

void Init()
{
    memset(out, 0, sizeof(out));
    memset(in, 0, sizeof(in));
    for (int i = 0; i < 26; i++)
        father[i] = i;
    memset(vis, 0, sizeof(vis));
}

int main()
{
    int T;
    cin >> T;
    int n;
    while (T--)
    {
        cin >> n;
        Init();
        while (n--)
        {
            scanf("%s", word);
            int u = word[0] - 'a';
            int v = word[strlen(word) - 1] - 'a';
            mergee(u, v);
            out[u] ++;
            in[v] ++;
            vis[u] = vis[v] = 1;
        }
        int cnt = 0, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < 26; i++)
        {
            if (vis[i] && father[i] == i)
            {
                cnt++;
            }
        }
        if (cnt > 1)
        {
            puts("The door cannot be opened.");
            continue;
        }
        bool flag = true;
        for (int i = 0; i < 26; i++)
        {
            if (vis[i] && out[i] != in[i])
            {
                if (out[i] - in[i] == 1)
                {
                    cnt1++;
                    if (cnt1 > 1)
                    {
                        flag = false;
                        break;
                    }
                }
                else if (in[i] - out[i] == 1)
                {
                    cnt2++;
                    if (cnt2 > 1)
                    {
                        flag = false;
                        break;
                    }
                }
                else
                {
                    flag = false;
                    break;
                }
            }
        }
        if (!flag) puts("The door cannot be opened.");
        else puts("Ordering is possible.");
    }
    return 0;
}

2018-04-03