PKU2723-Get Luffy Out

題目：http://poj.org/problem?id=2723
有N對鑰匙、M層樓，編號X的鑰匙可以開編號X的門
其中這N對鑰匙中的每一對，都只能從兩把鑰匙中選一把帶在身上
(對於p,q這對鑰匙，選了p的話q就會消失，反之亦然)

而這M層順序分別1F,2F,3F,...,MF，各層樓也有兩道門
只要打開其中一道門就能通過該層樓了

現在Luffy被關起來了，他的好朋友Ratish要去救他
對每筆給定的鑰匙以及門組合，請問Ratish最多可以爬到幾層樓？
(到達5F即1F,2F,3F,4F,5F都成功通過)

(2011.12.16補上解題報告)

程式碼：http://codepad.org/DkNBPd2n
題單是來自(不確定是否是原著)：http://zakir.is-programmer.com/posts/21610.html

這就是經典的2-SAT問題(二元滿足性問題)
每一對鑰匙都是"互斥"的，選了p就不能選q、選q就沒p可用
然而對每一層樓的兩道門，都得至少開一道門才能通過

如果存在通過7層的方案，那麼6,5,4,...層也肯定能通過
要是不可能到達9層，那麼10,11,12,...當然也別想
所以我們二分答案
每次檢查，都用前x樓的門組合進行構圖
(現在已經變成這x對門，都最起碼得開一道)
比如說有層樓門編號(a,b)、他們分屬兩個互斥組(a,p)和(b,q)
想開a門的話，那麼肯定沒p鑰匙可用
如果選擇開b門，q鑰匙就會消失

構圖完成後，利用Tarjan法(或K某法)找強連通分量，
如果有任何互斥點在同一個強連通裡，那就說明了這圖不可能滿足

構圖細節可以見程式碼