関節点，二重頂点連結成分分解

説明

無向グラフ g に対して関節点と二重頂点連結成分が次のように定義される．

• 頂点 u が関節点である iff g から u を除いたグラフが非連結．
• 辺の集合 es が二重頂点連結成分である iff es に制限したグラフは関節点を含まない．

すべての関節点とすべての二重頂点連結成分を求めるためには深さ優先探索を用いればよい．

以下のプログラムは関節点と二重頂点連結成分を同時に求めている．処理の流れは同じだが求める部分のコードが分離しているので，どちらか一方だけ必要な場合は適当に消して使うほうが短い．

計算量

O(E log V)

log V は set を用いて辺集合を管理するためにかかるコストである．二重頂点連結成分がいらない場合はこれを削除することで O(E) にできる．

使い方

const Graph& g

無向グラフ．任意の辺 (u,v) に対して逆辺 (v,u) を持つグラフとして表現する．

vector<int>& art

関節点のリストが入る．ある関節点 u が k 個の二重連結成分をつないでいる場合，(k-1) 個の u が入る．

vector<Edgeset>& bcomp

二重連結成分をあらわす辺集合のリストが入る．

ソースコード

struct UndirectionalCompare {
  bool operator() (const Edge& e, const Edge& f) const {
    if (min(e.src,e.dst) != min(f.src,f.dst))
      return min(e.src,e.dst) < min(f.src,f.dst);
    return max(e.src,e.dst) < max(f.src,f.dst);
  }
};
typedef set<Edge, UndirectionalCompare> Edgeset;
void visit(const Graph &g, int v, int u,
    vector<int>& art, vector<Edgeset>& bcomp,
    stack<Edge>& S, vector<int>& num, vector<int>& low, int& time) {
  low[v] = num[v] = ++time;
  FOR(e, g[v]) {
    int w = e->dst;
    if (num[w] < num[v]) S.push(*e);              // for bcomps
    if (num[w] == 0) {
      visit(g, w, v, art, bcomp, S, num, low, time);
      low[v] = min(low[v], low[w]);
      if ((num[v] == 1 && num[w] != 2) ||         // for arts
          (num[v] != 1 && low[w] >= num[v])) art.push_back(v);
      if (low[w] >= num[v]) {                     // for bcomps
        bcomp.push_back(Edgeset());
        while (1) {
          Edge f = S.top(); S.pop();
          bcomp.back().insert(f);
          if (f.src == v && f.dst == w) break;
        }
      }
    } else low[v] = min(low[v], num[w]);
  }
}
void articulationPoint(const Graph& g,
    vector<int>& art, vector<Edgeset>& bcomp) {
  const int n = g.size();
  vector<int> low(n), num(n);
  stack<Edge> S;
  REP(u, n) if (num[u] == 0) {
    int time = 0;
    visit(g, u, -1, art, bcomp, S, num, low, time);
  }
}

Verified

二重連結成分はチェックされていない．

• UVA 10765 (Doves and bombs), 506 MS, 5148 KB (連結成分を消すと 227 MS, 3332 KB)
• UVA 10199 (Tourist Guide), 295 MS, 604 KB (ただし連結成分を消した)