lowlinkを使わずに橋・関節点を求める

橋や関節点を求める方法としては、lowlinkを使う方法が一般的です。しかし、~~逆張り精神から~~橋をimos法で求める方法に感動して(参考:AtCoder Regular Contest 039 解説)関節点も求められないか？ということで今回はimos法を使って実装します。計算量は橋、関節点ともにO(V+E)です(UnionFindの計算量を定数とした)

どうやって求めるか

橋

まずグラフに対して全域木を考えます。全域木に使われなかった辺は、ある頂点とその祖先を結ぶ辺（後退辺）になっています。そこで、すべての後退辺に対して深いほうの頂点に+1,浅いほうの頂点に-1を足します。すると、すべての頂点 $i$ について

$i$ と $i$ の親を結ぶ辺が橋 $\Leftrightarrow$ $i$ の部分木の和が $0$

が成り立ちます。また、後退辺は橋にはなりません。したがって、全域木の帰りがけ順に計算することで、橋を全列挙することができます。下のコードでは、imos[ $i$ ]が対応する部分木の和になっています。ここで $i$ の部分木の和は「 $i$ の部分木から外に出ている後退辺の数になる」ことに注意してください。

関節点

関節点については、

$i$ が関節点 $\Leftrightarrow$ $i$ のある子が存在して、その部分木と $i$ の祖先とを結ぶ後退辺が存在しない

が成り立ちます。 $i$ に繋がっている後退辺がないなら橋と同じように帰りがけ順に計算できるのですが、後退辺が $i$ 自身とつながっている場合もあるので工夫が必要です。 $i$ と直接つながっている子孫 $j$ について、 $j$ が $i$ の直接の子でないならimos[( $i$ の子のうち部分木として $j$ を含む頂点)]から1を引いていきます。ここで引いたのは $j$ と $i$ を結ぶ後退辺に対応しています。 $i$ の子 $k$ について、引かれる前のimos[ $k$ ]は「 $k$ の部分木から外に出ている後退辺の数」で,引かれた後のimos[ $k$ ]は「 $k$ の部分木から外に出ている後退辺のうち、 $i$ と直接つながっているものを除いた数」なので、この値が0になるとき、 $i$ は関節点になります。これを帰りがけ順にやっていくことで、すべての関節点が列挙できます。なお、 $i$ とつながっているのが $i$ の子孫であるかどうかを判定するために、下のコードではactiveという配列を用意しています。また、 $i$ の子孫 $j$ がどの部分木に含まれているかを判定するために、unionfindを使っています。unionfindではuniteの順番を工夫することで、必ずrootが一番根に近くなるようにしています。

実装

まず1回目のdfsで各後退辺を求め、深いほうの頂点に+1,浅いほうの頂点に-1をしています
2回目のdfsで累積和を求めるとともに求めた累積和から上のようにして関節点を求めています。unionfindのrootが $i$ 自身になってしまっては困るため、unionfindのタイミングをずらしています。また根については別に関節点かどうかを判定する必要があります。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define ITR(x, c) for(__typeof(c.begin()) x = c.begin(); x != c.end(); x++)
#define all(v) v.begin(), v.end()
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans = 0;
vl g[MAX_N];
vl visited(MAX_N, 0), imos(MAX_N, 0), active(MAX_N, 0);
vl iskansetu(MAX_N, 0);
struct union_find {
    ll par[MAX_N];
    ll Size[MAX_N];
    union_find(ll n) {
        for(int i = 0; i < n; i++) {
            par[i] = i;
            Size[i] = 1;
        }
    }
    ll root(ll x) {
        if(par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }
    bool same(ll x, ll y) { return root(x) == root(y); }
    void unite(ll x, ll y) {
        if(same(x, y))
            return;
        Size[root(x)] += Size[root(y)];
        par[root(y)] = root(x);
    }
};
union_find uni(MAX_N);
void dfs(ll x) {
    visited[x] = 1;
    active[x] = 1;
    for(ll i : g[x]) {
        if(visited[i] == 0) {
            dfs(i);
        } else {
            if(active[i]==0) {//すでに訪れていてすでに探索が終わっている頂点とを結ぶ辺は後退辺
                imos[x]--;
                imos[i]++;
            }
        }
    }
    active[x] = 0;
}
void dfs2(ll x) {
    visited[x] = 1;
    active[x] = 1;
    vl A;
    for(ll i : g[x]) {
        if(visited[i] == 0) {
            dfs2(i);
            imos[x] += imos[i];
            if(imos[i])
                A.push_back(i);　//imos[i]が正なら後でunite
        }
    }

    for(ll i : g[x]) {
        if(active[i] == 0) {    //すでに探索が終わっている=子孫
            if(uni.root(i) == i) {　//iがxの子であるとき
                if(imos[uni.root(i)] == 0)
                    iskansetu[x] = 1;
            } else {                       //iがxの直接の子でない子孫のとき
                imos[uni.root(i)]--;   
                if(imos[uni.root(i)] == 0)
                    iskansetu[x] = 1;
            }
        }
    }

    for(ll i : A)
        uni.unite(x, i);

    active[x] = 0;
}

int main() {
    cin >> n >> m;
    rep(i, m) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    rep(i, n) {
        if(!visited[i])
            dfs(i);
    }

    visited = vl(n, 0);

    rep(i, n) {
        if(!visited[i]) {
            dfs2(i);
            iskansetu[i] = 0;
            for(ll j : g[i]) {
                if(!uni.same(g[i][0], j))
                    iskansetu[i] = 1;
            }
        }
    }

    rep(i, n) {
        if(iskansetu[i])
            cout << i << endl;
    }
}

verify:
https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_A