CF547D 题解
这题有两个很妙的做法。
做法 1
网格图
- 点 ---> 边
- 横纵坐标 ---> 点
对于每个点，将横纵坐标之间连一条边。
转化为无向图欧拉回路定向问题。
做法 2
直接“乱搞”。
考虑对于每个横纵坐标随便配对连线二分图染色，发现一定是二分图，因为边只有横边与纵边，且每种边数量 \(\le 1\)，最终的简单环必定是交错的。
这题有两个很妙的做法。
网格图
对于每个点，将横纵坐标之间连一条边。
转化为无向图欧拉回路定向问题。
直接“乱搞”。
考虑对于每个横纵坐标随便配对连线二分图染色，发现一定是二分图，因为边只有横边与纵边，且每种边数量 \(\le 1\)，最终的简单环必定是交错的。