ei1333's page

ホーム > Wiki

二重辺連結成分分解(Biconnected-Components)

説明

二重辺連結成分分解する。

計算量

$O(V + E)$

実装例

struct BiConnectedComponents
{
  UnionFind uf;
  vector< vector< int > > g;
  vector< pair< int, int > > edges;
  vector< int > used, ord, low, comp;

  BiConnectedComponents(size_t v) : uf(v), g(v), used(v, 0), comp(v), ord(v), low(v)
  {
  }

  void add_edge(int x, int y)
  {
    g[x].push_back(y);
    g[y].push_back(x);
    edges.push_back(minmax(x, y));
  }

  void dfs(int idx, int &k, int par = -1)
  {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];

    for(auto &to : g[idx]) {
      if(!used[to]) {
        dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        if(ord[idx] >= low[to]) uf.unite(idx, to);
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
  }

  int operator[](int k)
  {
    return (comp[k]);
  }

  size_t size()
  {
    return (g.size());
  }

  void build(vector< vector< int > > &t)
  {
    int kk = 0;
    dfs(0, kk);

    int ptr = 0;
    vector< int > cc(g.size());
    for(int i = 0; i < g.size(); i++) {
      if(i == uf.find(i)) cc[i] = ptr++;
    }

    t.resize(ptr);
    for(int i = 0; i < g.size(); i++) {
      comp[i] = cc[uf.find(i)];
    }
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      t[x].push_back(y);
      t[y].push_back(x);
    }
  }
};

問題例