CF 732 F - Tourist Reform
問題
問題概要
頂点辺の無向グラフがある。このグラフは連結であり、多重辺や自己ループは存在しない。さて、この辺を全て有向辺に変更することを考える。有向辺に変更した後のグラフ上で、を「頂点を始点としたときに訪れることの出来る頂点数」と定義したとき、もとの無向グラフの辺情報が与えられるのでこのの最小値を最大化するように無向辺を有向辺に変更する方針と、その最小値を最大化した時の値を示せ。
アイデア
橋と二重辺連結成分分解というのがキーワードになる。橋というのは「その辺を取り除くとグラフが非連結になるような辺」のことを指す。そして二重辺連結成分分解とは、橋を含まない連結成分(つまり連結成分内の辺のどれか1つを取り除いてもその連結性が保たれる)にグラフを分解することを指す(有向グラフで言う強連結成分分解みたいな感じ)。
そうすると、連結成分内では適切に有向辺の向きを決めれば、それを強連結成分とすることができる。実際にどうすればいいかというと、強連結成分分解のときのようにdfsして辺の向きを決定していけばいい。
連結成分内では互いに行き来が可能とわかれば、あとは橋の向きをどうすればいいかを決めればよいが、最大の連結成分に向かっていく方向に橋の向きを向けるのが、最小値を最大化出来るので、最大のサイズの連結成分の適当な頂点からdfsをして、まだその辺の向きが決まってなければ次の頂点から今いる頂点へ辺の向きを決定すれば、この最大値は連結成分の内最大のもののサイズとなる。
橋と二重辺連結成分分解を利用する類題として以下の2つがある(練習とverifyを兼ねて解いた)。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef vector<int> vi; typedef vector<bool> vb; typedef pair<int,int> edge; typedef pair<int,int> pi; vector<vi> G; void bridge_dfs(int now, int from, vector<edge> &bridge, vector<vi> &bicomp, stack<int> &roots, stack<int> &S, vb &inS, vi &preord, int &pre_ct){ preord[now] = pre_ct++; S.push(now); inS[now]=true; roots.push(now); rep(i,G[now].size()){ int to = G[now][i]; if(preord[to] == -1) bridge_dfs(to,now,bridge,bicomp,roots,S,inS,preord,pre_ct); else if(from != to && inS[to]) while(preord[roots.top()] > preord[to]) roots.pop(); } if(now == roots.top()){ bridge.pb(edge(now,from)); bicomp.pb(vi()); while(1){ int v=S.top(); S.pop(); inS[v]=false; bicomp.back().pb(v); if(now == v) break; } roots.pop(); } } void bridge_detect(vector<edge> &bridge, vector<vi> &bicomp){ const int n=G.size(); vi preord(n,-1); vb inS(n,false); stack<int> roots,S; int pre_ct=0; rep(i,n)if(preord[i] == -1){ bridge_dfs(i,n,bridge,bicomp,roots,S,inS,preord,pre_ct); bridge.pop_back(); } } edge e[400000]; int edge_used[400000]={0}; vector<vector<pi>> dG; void dfs(int v) { rep(i,dG[v].size()) { int to = dG[v][i].fi; int e_id = dG[v][i].se; if(!edge_used[e_id]) { e[e_id]=edge(to,v); edge_used[e_id]=1; dfs(to); } } } int main() { int n,m; scanf(" %d %d", &n, &m); G = vector<vi>(n); dG = vector<vector<pi>>(n); rep(i,m) { int u,v; scanf(" %d %d", &u, &v); --u; --v; if(u>v) swap(u,v); G[u].pb(v); G[v].pb(u); dG[u].pb(pi(v,i)); dG[v].pb(pi(u,i)); e[i]=edge(u,v); } vector<edge> bridge; vector<vi> bicomp; bridge_detect(bridge, bicomp); int ans=0; int largest_group_id=-1; vector<int> group(n); rep(i,bicomp.size()) { int B=bicomp[i].size(); if(ans<B) { ans=B; largest_group_id=i; } rep(j,B) group[bicomp[i][j]]=i; } dfs(bicomp[largest_group_id][0]); printf("%d\n", ans); rep(i,m) printf("%d %d\n", e[i].fi+1, e[i].se+1); return 0; }