题意:
连接圆周上标号 [ 0 .. n-1 ] 的点, 连接线可以放在圆内或圆外,但不能交叉(叠放). 给出点的个数n和相连的边(点对).判断是否可行.
思路:
2-SAT简单版:
将每条连接线看成两个点, 分别表示在圆内, 圆外. 实际中这两个点能且只能取其一.
枚举两根连接线的所有组合情况, 根据连接线所连两点的标号判断二者是否回相交.
若会, 则必然一个在圆内, 一个在圆外. 这两条连接线的状态是绑定的, 据此连线(无向图).
Tarjan求出强连通分量,
枚举每一条连接线, 判断它的两种状态是否在同一个强连通分量中. 若是, 矛盾. 否则可行.
**这最后......
阅读全文