King's Quest (UVa Live Archive Europe - Northeastern - 2003/2004 St. Petersburg (Russia))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2966

問題

頂点数2Nの2部グラフと完全マッチングの解1つが与えられる。ある1つの辺を使用するとしても完全マッチングが存在するような辺を全て求めよ。
1<=N<=2000
辺数<=20000

解法

フロー分解定理で解く。考え方としてはある辺を固定したときに最大流の解が存在するかどうかを確かめれば良い。それは与えられた完全マッチングの残余グラフ上でその辺を使用する閉路が存在するかどうかどうかと等価である。なのでdfsなどで2部グラフの片側の各頂点から自分自身へ戻れる一歩手前の頂点を全て列挙してやれば良い。TLEがゆるいのでO(20000*N)でも間に合う。