Spaghetti Source logo

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

説明

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

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

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

計算量

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

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

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.08.10 09:40:05.