読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

橋と関節点, lowlink

lowlink という概念について説明しています. 実装は簡単ですが, いろいろと応用が効いて面白いです.


無向連結グラフ$G(V, E)$ を考える. ここで, $|V| = n,\ |E| = m $ とする. このとき, 任意の$v \in V$ を始点として深さ優先探索を行うと深さ優先探索(DFS tree) ができる. DFS tree は頂点$v$ を根とする根付き木となる. DFS tree で用いられなかった$m - n + 1$ 個の辺を後退辺 と呼ぶ.


このとき, DFS tree での頂点$v$ の訪問時刻を$ord_v$, 後退辺を高々1 度だけ用いて到達することができる頂点の$ord$ の値の最小値(lowlink) を$low_v$ とする. lowlink を用いることでグラフの面白い性質を知ることができる.

その例として, 効率的にグラフの(bridge) と関節点(articulation point) を求めるアルゴリズムを記す.

グラフの橋とは, $G - e$ の連結成分の個数が増えるような辺$e$ のことである. 同様に, グラフの関節点とは, $G - v$ の連結成分数が増えるような頂点$v$ のことである.

明らかにDFS tree の後退辺は橋になり得ない. そこで, $O(n)$ 個の辺を取り除いたときの連結性を判定する$O(n(n+m))$ 時間の単純なアルゴリズムが考えられるが, lowlink を用いることで$(u,\ v)$ が橋 $ \Leftrightarrow ord_u < low_v $ となることがわかる. (これは, 後退辺で遡っても$u$ の訪問時刻より早い頂点に訪れることが不可能である, ということを示している.) これはlowlink を求めるDFS を行いながら$O(1)$ 時間で判定ができるので, $O(n+m)$ 時間で橋を列挙することができる.

関節点もすべての頂点とそれに接続される辺を除いたグラフの連結性を判定する$O(n(n+m))$ 時間のアルゴリズムが考えられるが, 橋の時の同様にlowlink を求めると効率的に判定が可能である. しかし, 少しだけ場合分けをする.

  • 頂点$u$ がDFS tree の根であるとき, その次数が1 より大きければ関節点である(明らかに木を(次数) 個の木に分断する.)
  • そうでないとき, 頂点$u$ のある子$v$ について$ord_u \leqq low_v$ が成り立てば頂点$u$ は関節点となる. ($u$ を介して親の方へ進まなければならないから, $u$ が消えると$v$ 以下の部分木は孤立してしまう.)

これも橋のときと同様に, $O(1)$ 時間で判定ができるので, $O(n+m)$ 時間で関節点を列挙できる.

ゆえに, lowlink の概念を用いることで$O(n+m)$ 時間で橋・関節点の判定を行える.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> G[1000000];
vector<pair<int, int> > bridge;
vector<int> articulation;
int ord[1000000], low[1000000];
bool vis[1000000];

void dfs(int v, int p, int &k)
{
	vis[v] = true;
	
	ord[v] = k++;
	low[v] = ord[v];
	
	bool isArticulation = false;
	int ct = 0;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]){
			ct++;
			dfs(G[v][i], v, k);
			low[v] = min(low[v], low[G[v][i]]);
			if (~p && ord[v] <= low[G[v][i]]) isArticulation = true;
			if (ord[v] < low[G[v][i]]) bridge.push_back(make_pair(min(v, G[v][i]), max(v, G[v][i])));
		}
		else if (G[v][i] != p){
			low[v] = min(low[v], ord[G[v][i]]);
		}
	}
	
	if (p == -1 && ct > 1) isArticulation = true;
	if (isArticulation) articulation.push_back(v);
}

int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		G[--x].push_back(--y);
		G[y].push_back(x);
	}
	
	int k = 0;
	for (int i = 0; i < n; i++){
		if (!vis[i]) dfs(i, -1, k);
	}
	
	sort(bridge.begin(), bridge.end());
	sort(articulation.begin(), articulation.end());
	
	printf("%d\n", articulation.size());
	
	for (int i = 0; i < articulation.size(); i++)
		printf("%d\n", articulation[i] + 1);
	
	printf("%d\n", bridge.size());
	
	for (int i = 0; i < bridge.size(); i++)
		printf("%d %d\n", bridge[i].first + 1, bridge[i].second + 1);
	
	
	return (0);
}