题意：要开启一扇门，n个单词是密码，n个单词中，如果一个单词的首字母和前一个单词的尾字母相同，并且每个单词都能这么连起来且只用一次，则门可以开启，否则不能开启，现给出单词，判断门是否可以开。
有向图欧拉通路充要条件：D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。
有向图欧拉回路充要条件：当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。 思路：一个单词关键是首字母和尾字母，可以把首字母和尾字母看成顶点，这个单词看成这两个顶点间的边，这么建图，于是原题就变成了找这个图中是否存在欧拉通路或者欧拉回路。建完图之后只需要根据定理判断每个顶点的出度、入度以及图的连通性即可。 转自：判断有多少个连通分量可以用并查集或者DFS。。我就都写了一遍
（其实是在给某人找错，就顺便写了一遍） 这是用并查集写的，写得不太好看。。（凑活看吧）#include#include 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#include #include 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]
