网站建设 石家庄,建设实验教学网站的作用,百度app下载最新版本,部署一个网站要做哪些工作题目链接#xff1a;Luogu P6066 [USACO05JAN] Watchcow S 欧拉回路 题目描述#xff1a; 给定一张无向图#xff0c;输出任意一条从一号结点出发的欧拉回路#xff08;欧拉回路指每条无向边来回经过且只经过一次#xff09;#xff0c;给定的图保证这样的欧拉回路存在。…题目链接Luogu P6066 [USACO05JAN] Watchcow S 欧拉回路 题目描述 给定一张无向图输出任意一条从一号结点出发的欧拉回路欧拉回路指每条无向边来回经过且只经过一次给定的图保证这样的欧拉回路存在。 题解 只需要从一号结点开始使用Hierholzer算法进行遍历即可。对于一个存在欧拉回路或者欧拉通路的图Hierholzer算法的思想是一直在图中找环每找到一个环就将这个环从图中删除。具体地 遍历到某个结点时找到一个以当前结点为起点的环如果不存在这样的环则退出从图中删除当前找到的环经过的边然后依次从当前的环上的每个点遍历即回到1。将遍历的当前结点加入到栈中。 上述的过程保存的结点依次从栈中弹出则是一条以传入结点开始的欧拉回路或者欧拉通路。 在实际实现中我们知道DFS算法可以找环所谓的删除边的操作我们则可以每遍历一条边即将边给删除这样只需要一次遍历即可找到欧拉回路或者欧拉通路因此时间复杂度为O(nm)对于边的删除操作如果使用邻接矩阵存边我们没访问一次便执行connect[u][v]--操作对于邻接表我们可以通过给每一条边增加一个deleted的标志遍历之后将deleted置为true或者使用一个cnt数组cnt[u]表示u结点应该从第几条边开始遍历每遍历一条边便使cnt[u]即可达到删除边的操作使用链式前向星也可以通过增加deleted标志来实现删除边的效果。具体可以参见代码实现。 特别地对于需要按照字典序进行遍历的情况而言我们需要使用邻接表存边这样才能够进行排序。除此之外对于有些题目会要求无向边只经过一次我们在删除边的时候需要将其反向边也给删除掉而如果使用邻接表进行存边的话我们需要保存反向边的编号同时对于自环需要额外注意反向边的编号差异而如果使用链式前向星则可以通过i^1的方式很容易的获取到反向边因此对于这种题目推荐使用邻接表保存排序后如果需要的话对邻接表进行遍历再通过链式前向星保存图由于链式前向星后加入的边会先遍历因此排序时往往需要逆序。 代码LuoguP6066
