拓扑排序。
前言:感觉不像网络流或者二分图啊...不会是他们说错了吧啊啊啊,不管了。
题目大意是要你找到一种定向方法,使图中不存在环。
考虑拓扑排序。
先将入读为的点加入队列(此时并不考虑无向边),再进行拓扑。
拓扑到点时,如果发现有一条无向边,就将它直接定向:现在节点为这条边的起点。
关于这种做法的正确性
“dfs完成拓扑排序,拓扑这个东西核心就是排序,排什么序呢,将无向图变成一个有向无环图(DAG),这个就是题目的要求吗,双边就不跑,只跑单边,把拓扑序找到,再依次判断方向。对于拓扑序来说,dfs后深度越浅的点,拓扑序越大,然后只将大的指向小的,就不会形成环了。“(@Zxsoul)
注:
- 使用时注意必须是奇数
- 当一道题目与 DAG(有向无环图)有关时,考虑拓扑排序。