ARC092 F : Two Faced Edges(1100)
作成日：2018.08.15
最終更新日：2018.08.15
問題概要
$1$から$N$までの番号が付いた$N$個の頂点と、頂点$a_i$から頂点$b_i$へ伸びる$M$本の有向辺からなるグラフがある。
辺の向きを反転させることでグラフの強連結成分の個数が変わるかを、すべての辺について判定せよ。
制約
$2 \leq N \leq 1000$
$1 \leq M \leq 2 \times 10^5$
$1 \leq a_i , b_i \leq N$
$a_i \neq b_i$
$i \neq j$ならば$(a_i,b_i) \neq (a_j,b_j)$
考え方
まず頂点$a$から頂点$b$へ伸びる辺$e$の向きを反転させた時(その辺を$\bar e$とする)に、ある2つの頂点$u,v$が同じ強連結成分に属しているかが変わる必要条件を考える。
$u,v$が同じ強連結成分に属すようになるのは、元々$u \rightarrow v$または$v \rightarrow u$の少なくとも一方のパスがなかったが、$\bar e$を通ればそのパスが生じる時である。
前者のパスがない場合は$u \rightarrow b$と$a \rightarrow v$、後者のパスがない場合は$v \rightarrow b$と$a \rightarrow u$は元々存在しなければならない。
このことから前者と後者のパスのいずれかがもしくは両方がなかったとしても、$e$を用いないパス$a \rightarrow b$が存在することが分かる。
また元々$b \rightarrow a$のパスは存在しないことも分かる。
$u,v$が同じ強連結成分に属さないようになるのは、元々$u \rightarrow v$または$v \rightarrow u$の少なくとも一方のパスは必ず$e$を含み、$e$以外のパス$a \rightarrow b$は存在しない時である。
前者のパスに$e$が含まれる場合は$u \rightarrow a$と$b \rightarrow v$、後者のパスに$e$が含まれる場合は$v \rightarrow a$と$b \rightarrow u$は元々存在することになる。
このことから前者と後者のパスのいずれかがもしくは両方に$e$が含まれたとしても、パス$b \rightarrow a$が存在することが分かる。
またこの場合、$\bar e$を用いることで$u,v$が同じ強連結成分に属するようにはならない。
以上をまとめると、[条件I]$e$以外のパス$a \rightarrow b$が存在する、[条件II]パス$b \rightarrow a$が存在する、のうち一方のみを満たすことが必要条件である。
また上の議論から、強連結成分が組み変わって個数が変わらないということはないことも分かる。
さらに、$u,v$をそれぞれ$a,b$とすることで必要条件は十分条件でもあることが分かる。
[条件I]を判定するのを各辺に対して愚直にやると$O(M(N+M))$かかり間に合わないので工夫する。
$a$から$b$へ伸びる辺$e$以外の辺を用いてパス$a \rightarrow b$があるかをdfsで判定する時、$a$から到達できる頂点をメモすることになる。
$a$から伸びる他の辺について判定する時も$a$から到達できる頂点をメモすることになるから、ここをまとめれば高速化できる。
辺$e$を使う前であれば、$a$から伸びる他の辺について判定していても$e$について判定しているとしても問題ない。
すなわち頂点$a$からdfsを行い、辺$e$を使う直前で$b$に到達できたかを判定すれば良さそうである。
このままだと$e$を使った後に使った辺で$b$に到達できるようになる場合を正しく判定できないが、これは頂点$a$から伸びる辺を使う順序を逆にすれば判定漏れを防ぐことができる。
これにより各頂点につき2回dfsを行えば、各辺について[条件I]が判定できることが分かる。
この時の計算量は$O(N(N+M))$であるから十分高速である。
また各辺について[条件II]を判定するのは、各頂点につき1回dfsを行えば$O(N(N+M))$でできる。
以上より、この問題は$O(N(N+M))$で解けることが分かる。
ソースコード
マクロ等はこちら
const int MC = 1024;
int N,M;
vector<P2> V[MC];
vector<P2> E;
bool ans[200010];
bool visited[MC];
void dfs(int q){
visited[q] = 1;
for(auto u : V[q]){
if(visited[u.first]) continue;
dfs(u.first);
}
}
int main(){
cin >> N >> M;
repp(i,0,M){
int a,b;
cin >> a >> b;
V[a].PB(MP(b,i));
E.PB(MP(a,b));
}
repp(i,1,N+1){
fill(visited,visited+MC,0);
visited[i] = 1;
repp(j,0,V[i].size()){
if(visited[V[i][j].first]) ans[V[i][j].second] = 1;
else dfs(V[i][j].first);
}
fill(visited,visited+MC,0);
visited[i] = 1;
repm(j,V[i].size()-1,-1){
if(visited[V[i][j].first]) ans[V[i][j].second] = 1;
else dfs(V[i][j].first);
}
}
repp(i,1,N+1){
fill(visited,visited+MC,0);
dfs(i);
repp(j,0,M) if(E[j].second == i && visited[E[j].first]) ans[j] ^= 1;
}
repp(i,0,M) cout << (ans[i] ? "diff" : "same") << endl;
return 0;
}解法まとめ
$a$から$b$へ伸びる辺を用いずに$a$から$b$に到達できるかを各辺について判定する。
これは各頂点から使う辺の順序を逆にしてdfsを2回行い、いずれかのdfsでその頂点から伸びる辺が使われる直前にその辺の終点に到達できているかを見れば良い。(24-37行)
各辺においてその辺の終点から始点に到達できるかは、各頂点においてdfsを1回行えば判定できる。(38-42行)
各辺について反転させると強連結成分の個数が変わるかは、上の2つのうちの一方のみが当てはまるかと同値である。(41,43行)