二重辺連結成分分解と聞いて
問題概要
n 頂点 m 辺の連結な無向単純グラフが与えられる。
2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。
できるだけ多くの辺を壊したい。うまく s, t を選んだときの壊せる辺の本数の最大値を求めよ。
制約
- 2 <= n <= 3×105
- n-1 <= m <= 3×105
解法
s-t パスの connectivity (連結度) に関する問題なので、フローを流すか、二重辺連結成分分解したくなる。今回は二重辺連結成分分解して、各連結成分を 1 つのノードにつぶすと全体としてツリーになる。
- 各連結成分については、どの辺を壊してもグラフが分断されることはない
- 連結成分同士をつなぐ各橋については、その辺を壊すとグラフが分断される
2 点 s, t としてツリーの直径を考えると、分断できる橋の個数が最大になる。まとめると、二重辺連結成分分解して得られたツリーの直径の長さを求めればよい。
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; typedef vector<vector<int> > Graph; namespace BridgeDecomposition { // results vector<vector<int> > scc; Graph newG; vector<int> cmp; vector<pair<int,int> > bridges; // intermediate results vector<int> ord, low, seen, parent; vector<int> comp; set<pair<int,int> > newGEdges; // DFS of BridgeDecomposition void DFSOfBridgeDecomposition(const Graph &G, int v) { static int time = 0; seen[v] = true; ord[v] = low[v] = time++; for (int i = 0; i < (int)G[v].size(); ++i) { int to = G[v][i]; if (seen[to]) { if (to != parent[v]) low[v] = min(low[v], low[to]); continue; } parent[to] = v; DFSOfBridgeDecomposition(G, to); low[v] = min(low[v], low[to]); if (low[to] > ord[v]) { bridges.push_back(make_pair(v, to)); } } } // reconstruct tree void MakeTreeDFS(const Graph &G, int v, int tempCmp) { seen[v] = true; cmp[v] = tempCmp; for (int i = 0; i < (int)G[v].size(); ++i) { int to = G[v][i]; bool sameComp = true; if (seen[to]) sameComp = false; if (binary_search(bridges.begin(), bridges.end(), make_pair(v, to)) || binary_search(bridges.begin(), bridges.end(), make_pair(to, v))) sameComp = false; if (!sameComp) { int toCmp = cmp[to]; if (toCmp == -1) continue; if (toCmp != tempCmp) { if (!newGEdges.count(make_pair(toCmp, tempCmp)) && !newGEdges.count(make_pair(tempCmp, toCmp))) { newGEdges.insert(make_pair(tempCmp, toCmp)); newG[tempCmp].push_back(toCmp); newG[toCmp].push_back(tempCmp); } } } else { MakeTreeDFS(G, to, tempCmp); } } comp.push_back(v); } // main solver void solve(const Graph &G) { int N = (int)G.size(); cmp.resize(N); ord.resize(N); low.resize(N); seen.resize(N); parent.resize(N); for (int i = 0; i < N; ++i) { seen[i] = false; parent[i] = -1; } bridges.clear(); for (int i = 0; i < N; ++i) { if (!seen[i]) { DFSOfBridgeDecomposition(G, i); } } sort(bridges.begin(), bridges.end()); scc.clear(); newG.clear(); newG.resize(N); newGEdges.clear(); for (int i = 0; i < N; ++i) { seen[i] = false; cmp[i] = -1; } int tempCmp = 0; for (int v = 0; v < N; ++v) { if (seen[v]) continue; comp.clear(); MakeTreeDFS(G, v, tempCmp); scc.push_back(comp); ++tempCmp; } newG.resize(tempCmp); } }; vector<int> Prev; pair<int,int> DiameterDFS(const vector<vector<int> > &G, int v, int p) { pair<int,int> res(v, 0); for (int i = 0; i < (int)G[v].size(); ++i) { if (G[v][i] == p) continue; pair<int,int> tmp = DiameterDFS(G, G[v][i], v); tmp.second++; if (tmp.second > res.second) { res = tmp; Prev[G[v][i]] = v; } } return res; } vector<int> Diameter(const vector<vector<int> > &G) { Prev = vector<int>((int)G.size(), -1); pair<int,int> leaf = DiameterDFS(G, 0, -1); Prev = vector<int>((int)G.size(), -1); pair<int,int> t = DiameterDFS(G, leaf.first, -1); vector<int> res; int cur = t.first; while (cur != -1) { res.push_back(cur); cur = Prev[cur]; } return res; } int main() { int n, m; cin >> n >> m; Graph G(n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; --a, --b; G[a].push_back(b); G[b].push_back(a); } BridgeDecomposition::solve(G); vector<int> diameter = Diameter(BridgeDecomposition::newG); cout << (int)diameter.size() - 1 << endl; }
