本文共 4262 字，大约阅读时间需要 14 分钟。

欧拉路径/并查集 - Play on Words - POJ 1386

题意：

有 N 个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。

你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。

请你编写一个程序，判断是否能达到这一要求。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N，表示盘子数量。

接下来 N 行，每行包含一个小写字母字符串，表示一个盘子上的单词。

一个单词可能出现多次。

输出格式

如果存在合法解，则输出”Ordering is possible.”，否则输出”The door cannot be opened.”。

数据范围

$1\le N\le 10^5,单词长度均不超过1000$

输入样例：

32acmibm3acmmalformmouse2okok

输出样例：

The door cannot be opened.Ordering is possible.The door cannot be opened.

分析：

建图：

$建图方式是重中之重，由于单词的数量在10^5数量级，$

$考虑到单词连接的方式是首尾相连，故我们可以将每个单词看作一条边，边的端点为首部字母和末尾字母。$

问题就转化为给定m条有向边，判断是否存在欧拉路径。

有向图的欧拉路径：

$①、所有点的入度与出度均相等。或者，$

$②、起点的出度比入度大1，终点的入度比出度大1，其他点的入度与出度相等。$

本题还需注意连通性问题：

$判断是否存在孤立点：$

$①、并查集：若存在两个点的祖宗节点不同，说明存在孤立点。$

$②、欧拉路径：dfs跑一遍欧拉路径，若经过的边的数量小于m，说明存在孤立点。$

方法一：欧拉路径：

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int N=30, M=100010;int T,n=26,m,cnt;int din[N],dout[N];int g[N][N];char str[1010];bool has_euler()    //判断充要条件{       int start=0,end=0;    for(int i=0;i<n;i++)        if(din[i]!=dout[i])        {               if(din[i]+1==dout[i]) start++;            else if(dout[i]+1==din[i]) end++;            else return false;        }            if(!(!start && !end || start==1 && end==1)) return false;  //同时确保了奇数度的点数量为偶数    return true;}void dfs(int u){       for(int i=0;i<n;i++)        if(g[u][i])        {               cnt++;            g[u][i]--;            dfs(i);        }}int main(){       scanf("%d",&T);    while(T--)    {           cnt=0;        memset(g,0,sizeof g);        memset(din,0,sizeof din);        memset(dout,0,sizeof dout);        scanf("%d",&m);        for(int i=0;i<m;i++)        {               scanf("%s",str);            int len=strlen(str);            int a=str[0]-'a', b=str[len-1]-'a';            g[a][b]++;            din[b]++, dout[a]++;        }                int S=0;        while(!dout[S]) S++;        for(int i=0;i<n;i++)            if(din[i]+1==dout[i])            {                   S=i;                break;            }        if(has_euler()) dfs(S);                if(cnt<m) puts("The door cannot be opened.");        else puts("Ordering is possible.");    }    return 0;}

方法二：并查集：

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int N=30, M=100010;int T,n=26,m;int p[N];int din[N],dout[N];bool st[N];char str[1010];int Find(int x){       if(p[x]!=x) p[x]=Find(p[x]);    return p[x];}bool is_connected()    //连通性判断{       int root=-1;    for(int i=0;i<n;i++)        if(st[i])        {               if(root==-1) root=Find(i);            if(root!=Find(i)) return false;        }    return true;}bool has_euler()    //判断充要条件{       int start=0,end=0;    for(int i=0;i<n;i++)        if(din[i]!=dout[i])        {               if(din[i]+1==dout[i]) start++;            else if(dout[i]+1==din[i]) end++;            else return false;        }            if(!(!start && !end || start==1 && end==1)) return false;  //同时确保了奇数度的点数量为偶数    return true;}int main(){       scanf("%d",&T);    while(T--)    {           for(int i=0;i<n;i++) p[i]=i;        memset(st,false,sizeof st);        memset(din,0,sizeof din);        memset(dout,0,sizeof dout);                scanf("%d",&m);        for(int i=0;i<m;i++)        {               scanf("%s",str);            int len=strlen(str);            int a=str[0]-'a', b=str[len-1]-'a';            din[b]++, dout[a]++;            st[b]=st[a]=true;            p[Find(a)]=Find(b);        }                if(is_connected() && has_euler()) puts("Ordering is possible.");        else puts("The door cannot be opened.");    }    return 0;}