강한 연결 요소

  • 연결(connectedness):
    • 그래프 GG의 모든 정점쌍에 대해, 경로가 있다면 GG는 연결되어 있다.
    • 즉, 임의의 한 정점에서 다른 모든 정점으로의 경로가 존재한다면 연결되어 있다.
  • 연결요소(connected component):
    • 최대로 연결된 부분그래프. (A maximal connected subgraph)
  • 강한 연결(strongly connectivity):
    • 유향 그래프 GG의 모든 정점쌍에 대해 양방향으로 경로가 존재한다면 GG는 강하게 연결되어 있다.
    • 즉, 모든 정점쌍이 양방향으로 연결되어 정점쌍 사이에 사이클이 만들어지는 경우.
  • 강한 연결요소(strongly connected component)
    • 최대로 강하게 연결된 부분그래프. (A maximal strongly connected subgraph)
    • 어떤 강한 연결을 가진 부분그래프보다 더 큰 강한 연결을 가진 부분그래프가 없는 경우.
    • 정점 하나가 SCC가 될 수 있다.
  • 문제: https://www.acmicpc.net/problem/2150

Kosaraju’s algorithm

def kosaraju(G):
    stack = []
    visited = [False] * len(G)

    def dfs(u, S):
       visited[u] = True
       for v in G[u]:
           if not visited[v]:
               dfs(v)
       S.append(u)

    for u in range(len(G)):
       visited[u] = True
       if not visited[u]:
           dfs(u)

    def dfs_R(v, S):
       S.append(v)
       for u in G[v]:
           if not visited[u]:
               visited[u] = True
               dfs_R(u, S)

    visited = [False] * N
    sccs = []
    while stack:
        u = stack.pop()
        if not visited[u]:
            visited[u] = True
            scc = []
            dfs_R(u, scc)
            sccs.append(scc)
  • 시간복잡도(인접리스트): O(V+E)O(|V| + |E|)
  • 시간복잡도(인접행렬): O(V2)O(|V|^2)

Tarjan’s algorithm

def tarjan(G):
    stack = []
    onstack = [False] * (V + 1)

    sccs = []
    lowlink = [0] * (V + 1)
    idxs = [-1] * (V + 1)
    idx = 0

    def dfs(u):
        nonlocal idx
        idx += 1

        idxs[u] = lowlink[u] = idx
        stack.append(u)
        onstack[u] = True

        for v in G[u]:
            if idxs[v] == -1:
                dfs(v)
                lowlink[u] = min(lowlink[u], lowlink[v])
            elif onstack[v]:
                lowlink[u] = min(lowlink[u], idxs[v])

        if idxs[u] == lowlink[u]:
            scc = []
            w = -1
            while u != w:
                w = stack.pop()
                scc.append(w)
                onstack[w] = False
            sccs.append(sorted(scc))

    for u in range(1, V + 1):
        if idxs[u] == -1:
            dfs(u)

    return sccs
  • 시간복잡도: O(V+E)O(|V|+|E|)

Path-based algorithm

def path_based(G):
    S = []
    B = []

    I = [0] * (V + 1)
    c = V

    def dfs(v):
        S.append(v)
        I[v] = S.top()
        B.append(I[v])

        for w in G[v]:
            if I[w] == 0:
                dfs(w)
            else:
                while I[w] < B.top():
                    B.pop()

        if I[v] == B.top():
            B.pop()
            c += 1
            while I[v] <= S.top():
                I[S.pop()] = c

    for v in range(1, V + 1):
        if I[v] == 0:
            dfs(v)

Reachability-based algorithm

이 문서를 인용한 문서