算法学习之路|Play On Words（欧拉道路+dfs）

题目大意：给出n个单词，问能否把这些单词首尾相接（每个单词第一个字母和上一个单词最后一个字母相同）

分析：把单词相接转换成26字母间的有向图，问题就转化成求有向图是否构成欧拉道路。

ac代码：

#include
#include
#include
#include
#define maxn 30
using namespace std;
int vis[maxn],G[maxn][maxn],f[maxn],in[maxn],out[maxn];
void dfs(int x)
{
    vis[x]=true;
    for(int i=0;i<maxn;i++)//向前搜索
    {
        if(G[i][x]&&!vis[i])
            dfs(i);
    }
    for(int i=0;i<maxn;i++)//向后搜索
    {
        if(G[x][i]&&!vis[i])
            dfs(i);
    }
}

int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--){
        memset(G, 0, sizeof(G));
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        memset(vis, 0, sizeof(vis));
        char str[1005];
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str);
            G[str[0]-'a'][str[strlen(str)-1]-'a']++;
            out[str[0]-'a']++;//出度
            in[str[strlen(str)-1]-'a']++;//入度
        }
        bool flag=true;
        int num1=0,num2=0;
        for(int i=0;i<maxn;i++)//判断入度出度是否满足条件
        {
             if(!flag) 
             break; 
            if(in[i]!=out[i])
            {
                 if(in[i]==out[i]+1)
                     num1++; 
                 else if(out[i]==in[i]+1)
                     num2++; 
                 else 
                 {
                     flag=false;
                     break; 
                 } 
            } 
        } 
        if(num1&&num2&&num1+num2>2)
            flag=false;
        if(flag)
        {
            for(int i=0;i<maxn;i++)
                if(out[i])
                {
                    dfs(i);
                    break;
                }
            bool flag2=true;
            for(int i=0;i<maxn;i++)//判断是否连通
            {
                if(in[i]&&!vis[i])
                {
                    flag2=false;
                    break;
                }
                if(out[i]&&!vis[i])//这个if可以去掉，重复了
                {
                    flag2=false;
                    break;
                }
            }
            if(flag2) printf("Ordering is possible.\n");
            else printf("The door cannot be opened.\n");
        }
        else
        {
            printf("The door cannot be opened.\n");
        }
    }
    return 0;
}

此处用的不是并查集而是dfs，因此会出现一个问题，如果只向前搜索可能会导致无环图没有完整遍历，比如从单词链中间某一个单词开始dfs的话，会使得这个单词之间的单词被忽略掉，因为是有向图，从而即使是从一个连通分量中的点（单词），也没有被标记过。

顺便回顾dfs，要注意边界条件。