強連結成分分解

date: 2021-06-09 excerpt: 強連結成分分解(scc)について

強連結成分分解(scc)について

双方向に参照してるループを高速に発見する技
- 強連結になっているループを検出し、各々のループを特定(ラベリングする、サイズをカウントする等)する

例; 強連結成分分解し、トポロジカルソートする

問題

AtCoder Library Practice Contest; G - SCC

解答

from typing import List, Any
import sys; sys.setrecursionlimit(10**9)

def dfs1(N: int) -> List[int]:
    """深さを記録する"""
    I = []
    used = [False]*N
    def _dfs(pos):
        used[pos] = True
        for i in G[pos]:
            if used[i] == False:
                _dfs(i)
        I.append(pos)
    for i in range(N):
        if used[i] == False:
            _dfs(i)
    return I

def dfs2(RI: List[int]) -> Any:
    """逆順に遅い値から見ていく
    遅い値から見るとdfs1でスキップされた経路を探索でき、
    その経路は巡回になっていれば閉じて終わる"""
    def _dfs(pos, grp):
        used[pos] = True
        grp.append(pos)
        for i in H[pos]:
            if used[i] == False:
                _dfs(i, grp)
    used = [False]*N

    igrp = []
    for i in RI:
        grp = []
        if used[i]:
            continue
        _dfs(i, grp)
        igrp.append(grp)
    return igrp

N,M=map(int,input().split())
G=[[] for _ in range(N)]
H=[[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    # a-=1; b-=1
    G[a].append(b)
    H[b].append(a)

I=dfs1(N)
igrp = dfs2(I[::-1]) ; """逆にしてインプットする"""
*igrp, = filter(lambda x:x, igrp)
l = len(igrp)
print(l)
for grp in igrp:
    print(len(grp), *grp[::-1])

例; 強連結している個数をノードをカウントする例

問題

競プロ典型 90 問; 021 - Come Back in One Piece

解説

https://github.com/E869120/kyopro_educational_90/blob/main/editorial/021.jpg

解答

from typing import List, Any
import sys; sys.setrecursionlimit(10**9)

def dfs1(N: int) -> List[int]:
    """深さを記録する"""
    I = []
    used = [False]*N
    def _dfs(pos):
        used[pos] = True
        for i in G[pos]:
            if used[i] == False:
                _dfs(i)
        I.append(pos)
    for i in range(N):
        if used[i] == False:
            _dfs(i)
    return I

def dfs2(RI: List[int]) -> Any:
    """逆順に遅い値から見ていく
    遅い値から見るとdfs1でスキップされた経路を探索でき、
    その経路は巡回になっていれば閉じて終わる"""
    class _h: # データホルダー
        cnt = 0
    def _dfs(pos):
        used[pos] = True
        _h.cnt += 1
        for i in H[pos]:
            if used[i] == False:
                _dfs(i)
    used = [False]*N
    ans = 0
    for i in RI:
        if used[i]:
            continue
        _h.cnt = 0
        _dfs(i)
        ans += _h.cnt * (_h.cnt - 1) // 2
    print(ans)
    return

N,M=map(int,input().split())
G=[[] for _ in range(N)]
H=[[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a-=1; b-=1
    G[a].append(b)
    H[b].append(a)

I=dfs1(N)
dfs2(I[::-1]) # 逆である