ZeroJudge g598 - 真假子圖 解題心得( 題目 )
這次一樣先提別人的作法，不過這些方法都行的通!
1.二分圖加二分搜(@thanksone):
這方法很難想到(普通建n次二分圖會TLE，但是要想到二分搜不簡單)
2.DSU(@peienwu @陳仲肯):
這個方法使用DSU跟undo，查詢幾乎可以達到線性時間。
這些解法可上https://hackmd.io/@peienwu/APCS1107 (C++)
回歸正傳!我的想法(我覺得這個想法比較簡單，但執行效率不知道:/)
解題概念:graph分群
注意:這個方法也許有bug，或是遇到極端測資會TLE(在ZJ上AC 0.4s, java)，所以先不貼碼。
解題方法:我們先分群，如果可以拜訪到的(pair、或是pair的pair、...)，反正有關連的都設為同個子圖(我們計為graph[i]=k，代表i在子圖j)，例如給予三個邊:1-2 2-3 4-5，則我們設graph[1]=graph[2]=graph[3]=1、graph[4]=graph[5]=2，也就代表我們有兩個子圖1、2，另外我們在dfs時要順便填原本的A、B組(我們表示為G[i])，我們一律先假設踩到的第一個為A，他旁邊的為B，再旁邊的又是A... 如下圖:
這樣我們就把初始的圖建好了!
再來是p組判定，分成兩種:
在同個graph:判斷G[i]是否相同，一樣就是錯的!
在不同graph:我們設flip[g]=k，如果flip=1代表翻轉，0代表不要，我們知道1是A，但4不一定是，但是我們前面還是那樣填入，所以flip的翻轉的用意是代表把g子圖的A修正為B，而B是修正為A，但是因為整個圖修正很麻煩，所以用一個變數來記。我們一開始設flip=-1代表未填入，之後如果遇到有一邊有填入過，而另一邊沒有，則我們比較兩個一不一樣(填過的那一邊是以填過的結果)，如果不一樣就把那個空的flip添入一樣的值，如果一樣就相反；如果遇到兩邊都填過的就比較結果，如果一樣就是錯的。
如下圖，假設第一組flip=0，如果加上一個邊1-4，則原本空的flip[2]要填入1(翻轉)才能符合，這時如果再加入一個3-5邊就是違法的。
可是最後還有個問題，哪一些flip初始填0，其實調查員給的邊也可以透過他兩端點屬於的graph形成幾個大子圖!(有可能多個因為有時有些還是沒連起來，所以還是互無關連)，dfs每一個子圖，而第一個就是填0的那一個!
