南宁市网站建设_网站建设公司_移动端适配_seo优化

【题目链接】

ybt 1528：【例 2】单词游戏

【题目考点】

1. 图论：欧拉图

• 有向图欧拉回路判定的充要条件：
  该图是弱连通图，所有顶点的入度等于出度。
• 有向图欧拉路径判定的充要条件：
  该图是弱连通图，只有一个顶点的出度比入度大1，一个顶点的入度比出度大1，其余顶点的入度等于出度。

【解题思路】

一个单词可以看作一个顶点，如果一个单词A的末尾字母和单词B的首字母相同，可以看作从顶点A到顶点B有一条有向边。本题要所有的单词首尾连接，即需要找到该图的一条欧拉路径（包括欧拉回路）。
首先判断该图是否存在欧拉路径。
输入一个单词，将单词的首尾字母转为顶点编号（字符a转为1，字符b转为2，…，字符c转为c-'a'+1）
单词的首字母表示的顶点到单词末尾字母表示的顶点设一条有向边，保存在邻接表中。
如果顶点A到顶点B有一条有向边，那么顶点A的出度增加1，顶点B的入度增加1。

判断该图是否存在欧拉路径，首先这个图应该是弱连通图，也就是说，将所有的边当做无向边，看这个无向图（原图的基图）是否为连通图，如果是，那么这个图是弱连通图。
判定一个无向图是否是连通图，可以使用深搜或广搜遍历图的方法，也可以使用并查集。
相关方法见：信息学奥赛一本通 1362：家庭问题(family)

本题使用并查集来判定该有向图的基图是否是连通图。将每条边连接的两个顶点所在的集合（连通分量）合并，最后统计集合的数量，即为该图的连通分量的数量。如果连通分量的数量为1，该图为连通图。
本题中不统计孤立点作为一个连通分量的情况，所以在看一个顶点是否为集合的根结点前，要先判断该顶点是否存在入度或出度。如果入度或出度大于0，该顶点就不是孤立点。

因为本题是判断一个图是否为欧拉图或半欧拉图。孤立点不与边相连，一个图是否是欧拉图，与孤立点的数量没有关系。尽管从概念上来说，一个孤立点也是一个连通分量，而本题应该统计有边参与的连通分量的数量，因此统计连通分量时应该不统计孤立点。

遍历所有的顶点：

• 如果顶点的入度等于出度，则跳过该顶点
• 统计入度比出度大1的顶点数量stNum与出度比入度大1的顶点数量edNum
• 如果出现其他情况，如顶点的入度与出度的差值大于等于2，或出度与入度的差值大于等于2，该图一定不是欧拉图或半欧拉图，不存在欧拉路径。

遍历结束后

• 如果stNum与edNum都为0，说明该图的所有顶点的入度与出度都相等，是欧拉图。
• 如果stNum与edNum都为1，说明该图存在1个入度比出度大1的顶点，存在一个出度比入度大1的顶点，其余顶点都入度等于出度，该图是半欧拉图。
• 其他情况，该图不是欧拉图或半欧拉图，不存在欧拉路径。

根据该图是否存在欧拉路径，输出结果。

【题解代码】

解法1：使用并查集判断基图是否为连通图

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=30;intt,n,cnt,fa[N],degIn[N],degOut[N];voidinitFa(intn){for(inti=1;i<=n;++i)fa[i]=i;}intfind(intx){returnx==fa[x]?x:fa[x]=find(fa[x]);}voidmerge(intx,inty){fa[find(x)]=find(y);}boolhasEulerPath(){intstNum=0,edNum=0;for(inti=1;i<=26;++i)if(degIn[i]!=degOut[i]){if(degIn[i]-degOut[i]==1)stNum++;elseif(degOut[i]-degIn[i]==1)edNum++;else//如果顶点i入度出度不等，或有多个入度比出度大1/出度比入度大1的顶点，或有入度出度差值不为1的顶点，则该图不存在欧拉路径returnfalse;}returnstNum==0&&edNum==0||stNum==1&&edNum==1;}intmain(){string s;cin>>t;while(t--){memset(degIn,0,sizeof(degIn));memset(degOut,0,sizeof(degOut));cnt=0;cin>>n;initFa(26);for(inti=1;i<=n;++i){cin>>s;intu=s.front()-'a'+1,v=s.back()-'a'+1;degIn[v]++,degOut[u]++;merge(u,v);}for(inti=1;i<=26;++i)if((degIn[i]>0||degOut[i]>0)&&fa[i]==i)//该顶点在连通图中，且该顶点是根结点cnt++;if(cnt==1&&hasEulerPath())cout<<"Ordering is possible.\n";elsecout<<"The door cannot be opened.\n";}return0;}

解法2：dfs判断基图是否为连通图

换一种写法进行欧拉图判定

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=30;intt,n,cnt,degIn[N],degOut[N],edge[N][N];boolvis[N];voiddfs(intu){vis[u]=true;for(intv=1;v<=26;++v)if(edge[u][v]&&!vis[v])dfs(v);}boolhasEulerPath(){boolhalfEuler=false,hasSt=false,hasEd=false;//halfEuler：是否为半欧拉图 hasSt：是否有出度比入度大1的顶点 hasEd：是否有入度比出度大1的顶点for(inti=1;i<=26;++i)if(degIn[i]!=degOut[i]){halfEuler=true;if(!hasEd&&degIn[i]-degOut[i]==1)hasEd=true;elseif(!hasSt&&degOut[i]-degIn[i]==1)hasSt=true;else//如果顶点i入度出度不等，或有多个入度比出度大1/出度比入度大1的顶点，或有入度出度差值不为1的顶点，则该图不存在欧拉路径returnfalse;}return!halfEuler||hasSt&&hasEd;}intmain(){string s;cin>>t;while(t--){memset(degIn,0,sizeof(degIn));memset(degOut,0,sizeof(degOut));memset(edge,0,sizeof(edge));memset(vis,0,sizeof(vis));cnt=0;cin>>n;for(inti=1;i<=n;++i){cin>>s;intu=s.front()-'a'+1,v=s.back()-'a'+1;edge[u][v]=edge[v][u]=1;//建原有向图的基图（无向图）degIn[v]++,degOut[u]++;}for(inti=1;i<=26;++i)if((degIn[i]>0||degOut[i]>0)&&!vis[i]){dfs(i);cnt++;}if(cnt==1&&hasEulerPath())cout<<"Ordering is possible.\n";elsecout<<"The door cannot be opened.\n";}return0;}