企业官网建设流程全解析

旅行社 网站系统,公共图书馆门户网站建设总结,谷歌seo推广,wordpress滑动解锁【题目链接】 ybt 1528#xff1a;【例 2】单词游戏 【题目考点】 1. 图论#xff1a;欧拉图 有向图欧拉回路判定的充要条件#xff1a; 该图是弱连通图#xff0c;所有顶点的入度等于出度。有向图欧拉路径判定的充要条件#xff1a; 该图是弱连通图#xff0c;只有一…【题目链接】ybt 1528【例 2】单词游戏【题目考点】1. 图论欧拉图有向图欧拉回路判定的充要条件该图是弱连通图所有顶点的入度等于出度。有向图欧拉路径判定的充要条件该图是弱连通图只有一个顶点的出度比入度大1一个顶点的入度比出度大1其余顶点的入度等于出度。【解题思路】一个单词可以看作一个顶点如果一个单词A的末尾字母和单词B的首字母相同可以看作从顶点A到顶点B有一条有向边。本题要所有的单词首尾连接即需要找到该图的一条欧拉路径包括欧拉回路。首先判断该图是否存在欧拉路径。输入一个单词将单词的首尾字母转为顶点编号字符a转为1字符b转为2…字符c转为c-a1单词的首字母表示的顶点到单词末尾字母表示的顶点设一条有向边保存在邻接表中。如果顶点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使用并查集判断基图是否为连通图#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN30;intt,n,cnt,fa[N],degIn[N],degOut[N];voidinitFa(intn){for(inti1;in;i)fa[i]i;}intfind(intx){returnxfa[x]?x:fa[x]find(fa[x]);}voidmerge(intx,inty){fa[find(x)]find(y);}boolhasEulerPath(){intstNum0,edNum0;for(inti1;i26;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;}returnstNum0edNum0||stNum1edNum1;}intmain(){string s;cint;while(t--){memset(degIn,0,sizeof(degIn));memset(degOut,0,sizeof(degOut));cnt0;cinn;initFa(26);for(inti1;in;i){cins;intus.front()-a1,vs.back()-a1;degIn[v],degOut[u];merge(u,v);}for(inti1;i26;i)if((degIn[i]0||degOut[i]0)fa[i]i)//该顶点在连通图中且该顶点是根结点cnt;if(cnt1hasEulerPath())coutOrdering is possible.\n;elsecoutThe door cannot be opened.\n;}return0;}解法2dfs判断基图是否为连通图换一种写法进行欧拉图判定#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN30;intt,n,cnt,degIn[N],degOut[N],edge[N][N];boolvis[N];voiddfs(intu){vis[u]true;for(intv1;v26;v)if(edge[u][v]!vis[v])dfs(v);}boolhasEulerPath(){boolhalfEulerfalse,hasStfalse,hasEdfalse;//halfEuler是否为半欧拉图 hasSt是否有出度比入度大1的顶点 hasEd是否有入度比出度大1的顶点for(inti1;i26;i)if(degIn[i]!degOut[i]){halfEulertrue;if(!hasEddegIn[i]-degOut[i]1)hasEdtrue;elseif(!hasStdegOut[i]-degIn[i]1)hasSttrue;else//如果顶点i入度出度不等或有多个入度比出度大1/出度比入度大1的顶点或有入度出度差值不为1的顶点则该图不存在欧拉路径returnfalse;}return!halfEuler||hasSthasEd;}intmain(){string s;cint;while(t--){memset(degIn,0,sizeof(degIn));memset(degOut,0,sizeof(degOut));memset(edge,0,sizeof(edge));memset(vis,0,sizeof(vis));cnt0;cinn;for(inti1;in;i){cins;intus.front()-a1,vs.back()-a1;edge[u][v]edge[v][u]1;//建原有向图的基图无向图degIn[v],degOut[u];}for(inti1;i26;i)if((degIn[i]0||degOut[i]0)!vis[i]){dfs(i);cnt;}if(cnt1hasEulerPath())coutOrdering is possible.\n;elsecoutThe door cannot be opened.\n;}return0;}