当前位置: 首页 > 工具软件 > Marco Polo > 使用案例 >

zoj 2103 Marco Popo the Traveler

钱瑞
2023-12-01

 

第二次做这种题了。

 

先判连通,然后判欧拉,再找出来符合题意的最短交换次数。。。

 

WA了数次,WA得我都快没信心了。不过还是找出来好多BUGs,改了之后,顺利AC。。。

 

先判断连通,用并查集,不连通的话直接No了。

 

BUGS之一就是,我把判有向图是否有欧拉道路用到这个上面了 = =。。。这个是无向图。无向图的话判断奇点(度为奇数)有无,有且仅有两个是欧拉通路,没有的话是欧拉回路,都可以。

 

其实我那个不算BFS。。。其实用队列纯属多余,因为每次入队只有一个,出队也只有一个 = =。。不过用队列挺清楚的。

 

如果有颜色和当前颜色一样,就先走这条路,颜色不变,如果没有和当前色一样的,就随便走和它连通的且没被走过的路,颜色变。

 

直到某个点没有路可走了,那一定是走完了,返回次数。

 

注意标记的时候一定是把正反两条边都给标记了。

 

 

 类似资料:

相关阅读

相关文章

相关问答