想法：
做最大匹配，做完可從llink[i]=j得到每條匹配的邊(i,j)，也就是(i,j)是可能的答案，但要確認這條邊(i,j)的唯一性。
例如Sample Input的第二個測資，做完最大匹配可得到(A,1)(B,2)兩條邊，最大匹配數為2，要確認(A,1)是否唯一，就把(A,1)這條邊去掉並且禁止，然後再做一次最大匹配，會變成得到(A,2)(B,1)，最大匹配數還是2，與數量原來一樣並沒有減少，因此可知(A,1)這條邊不唯一。同理(B,2)也把它去掉並禁止，再做一次最大匹配，如果最大匹配數比原本小，這條邊就是答案可以輸出，反之如果最大匹配數和原本一樣，則這條邊不唯一不能輸出。
從底下code可以看到最大匹配的模板函數Bipartite(int n, int u, int v)多了兩個參數u, v，表示做最大匹配的時候禁止(u,v)這條邊的使用(line 65)。
UVa版：
POJ版：
沒有留言:
張貼留言