けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Educational Codeforces 046 E - We Need More Bosses

二重辺連結成分分解と聞いて

問題へのリンク

問題概要

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;
}