题意：要开启一扇门，n个单词是密码，n个单词中，如果一个单词的首字母和前一个单词的尾字母相同，并且每个单词都能这么连起来且只用一次，则门可以开启，否则不能开启，现给出单词，判断门是否可以开。
有向图欧拉通路充要条件：D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。
有向图欧拉回路充要条件：当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。
思路：一个单词关键是首字母和尾字母，可以把首字母和尾字母看成顶点，这个单词看成这两个顶点间的边，这么建图，于是原题就变成了找这个图中是否存在欧拉通路或者欧拉回路。建完图之后只需要根据定理判断每个顶点的出度、入度以及图的连通性即可。
转自：http://blog.csdn.net/zzzz40/article/details/38659755?utm_source=tuicool&utm_medium=referral
判断有多少个连通分量可以用并查集或者DFS。。我就都写了一遍
（其实是在给某人找错，就顺便写了一遍）
这是用并查集写的，写得不太好看。。（凑活看吧）
#include <cstdio>
#include <cstring>
using namespace std;
char a[1050],vis[26],VIS[26],f[26];
int cases,n,out[26],in[26],tot=0,temp,ans,ansx,ansy,len;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
scanf("%d",&cases);
while(cases--){
temp=ans=ansx=ansy=0;
for(int i=0;i<26;i++)f[i]=i;
memset(vis,0,sizeof(vis));
memset(VIS,0,sizeof(VIS));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a);
len=strlen(a)-1;
a[0]-='a',a[len]-='a';
out[a[0]]++,in[a[len]]++;
if(!vis[a[len]])vis[a[len]]++;
f[find(a[len])]=find(a[0]);
}
for(int i=0;i<=25;i++)
if(vis[i]&&!VIS[find(i)])
VIS[find(i)]++,ans++;
if(ans>1){puts("The door cannot be opened.");continue;}
for(int i=0;i<=25;i++){
if(in[i]-out[i]==1)ansx++;
else if(out[i]-in[i]==1)ansy++;
else if(in[i]!=out[i])temp++;
}
if(ansx==ansy&&(ansx==1||ansx==0)&&!temp)puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
}DFS：
#include <cstdio>
#include <Cstring>
#include <algorithm>
using namespace std;
char a[1005];
bool vis[26],VIS[26],flag;
int cases,tot,v[200010],next[200010],first[2010],n,in[26],out[26];
int cnt1,cnt2,cnt3;
void add(int x,int y){v[tot]=y;next[tot]=first[x];first[x]=tot++;}
void dfs(int x){
for(int i=first[x];~i;i=next[i])
if(!VIS[v[i]])VIS[v[i]]=1,dfs(v[i]);
}
int main(){
scanf("%d",&cases);
while(cases--){
flag=1;tot=cnt1=cnt2=cnt3=0;
memset(first,-1,sizeof(first));
memset(vis,0,sizeof(vis));
memset(VIS,0,sizeof(VIS));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a);
int len=strlen(a)-1;
a[0]-='a';a[len]-='a';
add(a[0],a[len]);
in[a[len]]++;out[a[0]]++;
vis[a[0]]=vis[a[len]]=1;
}
for(int i=0;i<26;i++){
if(in[i]!=out[i])cnt3++;
if(in[i]==out[i]-1)cnt1++;
if(out[i]==in[i]-1)cnt2++;
}
if(cnt3==2&&cnt1==1&&cnt2==1)
for(int i=0;i<26;i++){
if(in[i]<out[i]){
VIS[i]=1,dfs(i);
for(int i=0;i<26;i++)
if(vis[i]!=VIS[i])flag=0;
break;
}
}
else if(!cnt3){
dfs(a[0]);VIS[a[0]]=1;
for(int i=0;i<26;i++)
if(vis[i]!=VIS[i])flag=0;
}
else {puts("The door cannot be opened.");continue;}
if(flag)puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
}