Codeforces #27 D Ring Road 2

題意﹕給了一個帶 $N$ 個頂點的環 $C_N$ ，現在要添加 $M$ 條邊，你可以把邊畫在環內，或是環外，但必須使得每條邊之間都不能相交(在末端相交除外)。問是否存在一個決定邊的畫法使得條件達成。保証邊連接不同的頂點，沒重邊。

最初有一個很直觀的想法﹕假設邊是 $e = (x, y)$ 且 $x < y$ ，設 $A_e = \{i: x < i < y\}$ ， $B_e = \{1 \cdots N\} - A_e - \{x, y\}$ ，則 $e$ 會把頂點集分開兩半，使得任意邊 $e' = (x', y'), x' \in A_e, y' \in B_e$ 必不能與 $e$ 有相同的畫法。我們稱 $e$ 和 $e'$ 是互斥的。

可惜之後有一個錯的想法。以為順著輸入每條邊，都更新使得互斥的點對的可用的畫法，如遇上某一點對沒有可用的畫法則判無解。這個算法是錯的，只是我未找到反例。

然後有另一個想法，就是基於兩個互斥的點對必須有不同的畫法。可以立刻聯想到的是若把點對看作一個頂點，互斥點對添加一條邊，則此構造圖 $G$ 有解若且僅若 $G$ 是二分的(即可以用兩種顏色為頂點著色)。這就是正確的解。

順帶一提，本題要求的添加邊使得解是一平面圖，但必須基於 $C_N$ 底下該圖仍是平面的。所以不用想平面圖測試的算法了。