Strongly Connected Components
방향 그래프에는 n개의 노드가 있으며, 노드는 0부터 n-1까지 번호가 매겨져 있습니다. 또한 edges 목록이 있으며, 여기서 [from, to]는 노드 from에서 노드 to로 향하는 간선입니다.
강한 연결 요소는 간선을 따라가서 모든 노드가 서로에게 도달할 수 있는 가장 큰 노드 그룹입니다. 각 노드는 정확히 하나의 요소에 속하며, 어떤 사이클에도 속하지 않는 노드는 그 자체로 하나의 요소를 이룹니다. 강한 연결 요소의 개수를 반환하세요.
함수
- ninteger
- 노드의 수
- edgesinteger-2d-array
- 방향이 있는 각 간선은 [from, to]로 표시됩니다.
- 반환값integer
- 강하게 연결된 구성 요소의 수
제약 조건
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]이고0 ≤ from, to < n이며from ≠ to- 어떤 간선도 두 번 나타나지 않습니다.
예제
- 입력
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- 출력
- 3
- 설명
- 노드 0, 1, 2는 루프를 형성하므로 서로 도달할 수 있습니다. 노드 3과 4는 서로를 가리킵니다. 노드 5는 4에 도달하지만 5로 돌아오는 경로는 없으므로, 혼자 있습니다. 구성 요소는 3개입니다.
- 입력
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- 출력
- 4
- 설명
- 노드 0과 1은 서로를 가리키며 하나의 연결 요소를 형성합니다. 2에서 3으로 가는 간선은 한 방향으로만 이어지므로 2와 3은 서로 별개의 연결 요소이고, 노드 4에는 간선이 전혀 없습니다. 연결 요소는 4개입니다.
후속 질문
전체 그래프를 하나의 강한 연결 요소로 만들려면 간선을 최소 몇 개 추가해야 할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
두 노드는 서로가 서로에게 도달할 수 있을 때 정확히 같은 컴포넌트를 공유합니다. 모든 노드에서 탐색을 시작하면 이를 확인할 수 있지만, 같은 간선을 반복해서 걷게 됩니다. 한 번의 깊이 우선 탐색으로 컴포넌트가 어디에서 시작하는지 알 수 있을까요?
깊이 우선 탐색에서 각 노드에 처음 도달하는 순서대로 번호를 매깁니다. 각 노드에 대해
low도 추적합니다. 이는 탐색 트리를 따라 내려간 다음 간선 하나를 따라 아직 열려 있는 구성 요소의 노드로 돌아가서 도달할 수 있는 가장 작은 번호입니다.low가 자신의 번호와 같은 노드는 해당 구성 요소의 첫 번째 노드입니다.방문한 노드들을 스택에 유지하세요. 노드의 탐색이 끝났을 때
low가 노드 자신의 번호와 같으면 스택에서 해당 노드까지 꺼내세요. 이 노드들은 하나의 컴포넌트를 이루므로 개수를 세세요. 한 테스트에서는 탐색 깊이가 5000개 노드에 이르므로, 재귀하는 대신 (노드, 다음 간선) 프레임을 담는 자체 스택을 사용하세요.
풀이
각 구성 요소를 하나의 점으로 축소하면 구성 요소들이 사이클이 없는 그래프를 이룹니다. Kosaraju 알고리즘과 Tarjan 알고리즘은 이를 이용해 O(n + E) 시간에 모든 구성 요소를 찾습니다. 여기서 E는 간선의 수입니다.
모든 노드에서 앞뒤로 검색
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
노드 u와 v는 서로에게 도달할 수 있을 때 정확히 같은 컴포넌트에 속합니다. 따라서 아직 컴포넌트가 없는 노드 s에 대해 간선을 따라 정방향으로, 그리고 뒤집힌 간선을 따라 역방향으로 탐색합니다. 두 탐색에서 모두 발견된 노드가 해당 노드의 컴포넌트입니다. 첫 번째 예시에서 0에서 정방향으로 탐색하면 0부터 4까지 발견되고, 역방향으로 탐색하면 0, 1, 2가 발견되므로 {0, 1, 2}는 하나의 컴포넌트입니다.
각 컴포넌트마다 그래프 대부분을 두 번 탐색해야 합니다. 5001개의 노드를 지나는 5000개 간선의 사슬에서는 모든 노드가 각각 하나의 컴포넌트이며, 탐색은 약 2.5 × 10^7개의 노드를 방문합니다.
알고리즘
- 모든 노드의 나가는 간선 목록과 들어오는 간선 목록을 만듭니다.
- 아직 구성 요소가 없는 다음 노드
s를 선택하고 새 구성 요소를 셉니다. - 나가는 간선을 따라
s가 도달하는 노드와 들어오는 간선을 따라s에 도달하는 노드를 표시합니다. - 두 탐색 모두에서 표시된 모든 노드는
s의 구성 요소에 포함됩니다. 모든 노드에 구성 요소가 하나씩 생기면 그 개수를 반환합니다.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countKosaraju 알고리즘: 두 번의 순회
핵심 아이디어
컴포넌트 그래프에서 어떤 컴포넌트는 나가는 간선이 없는 싱크이며, 그 안에서 시작한 탐색은 정확히 해당 컴포넌트만 찾습니다. Kosaraju 알고리즘은 각 탐색이 그렇게 동작하도록 순서를 정합니다.
첫 번째 패스에서는 각 노드의 깊이 우선 탐색이 끝날 때마다 그 노드를 기록합니다. 두 번째 패스에서는 같은 컴포넌트들로 이루어진 역방향 그래프를 탐색하며, 가장 마지막에 끝난 노드부터 시작합니다. 컴포넌트 B에서 C로 향하는 간선이 있다면, B의 마지막 노드는 C의 모든 노드보다 나중에 끝납니다. 따라서 두 번째 패스가 C에 도달할 때는 C로 들어가는 간선이 있는 모든 컴포넌트가 이미 할당되어 있고, 역방향 그래프에서는 탐색이 C를 벗어날 수 없습니다.
첫 번째 예에서는 노드가 4, 3, 2, 1, 0, 5 순서로 끝납니다. 두 번째 패스에서는 차례로 {5}, {0, 1, 2}, {3, 4}를 찾습니다.
알고리즘
- 나가는 간선 목록과 들어오는 간선 목록을 만듭니다.
- 방문하지 않은 각 노드에서 반복적 깊이 우선 탐색을 실행하고, 탐색이 끝날 때마다 각 노드를
order에 추가합니다. order를 끝에서부터 순회합니다. 컴포넌트에 속하지 않은 각 노드에 대해 새 컴포넌트 하나를 세고, 해당 노드에서 들어오는 간선을 따라 탐색하여 도달하는 미할당 노드를 모두 할당합니다. 개수를 반환합니다.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countTarjan 알고리즘: low 값을 사용한 한 번의 순회
핵심 아이디어
깊이 우선 탐색을 한 번 실행하고 각 노드에 도달한 순서대로 번호를 매깁니다. 이 번호가 해당 노드의 index입니다. 방문한 노드 중 아직 컴포넌트가 열려 있는 노드를 스택에 유지하고, 값 low도 관리합니다. low는 탐색 트리를 따라 내려간 다음 스택에 있는 노드로 간선 하나를 거슬러 올라가 도달할 수 있는 가장 작은 인덱스입니다.
노드의 탐색이 끝났을 때 low가 index보다 작으면, 그 노드 아래의 무언가가 더 앞서 방문한 열린 노드까지 거슬러 올라가므로 해당 노드는 스택에 남습니다. 두 값이 같으면 그 노드는 탐색이 해당 컴포넌트에서 가장 먼저 진입한 노드입니다. 스택에서 그 노드까지 노드를 꺼내고 컴포넌트 하나를 셉니다. 이미 스택에서 꺼낸 노드로 향하는 간선은 다시 거슬러 올라갈 수 없는 완료된 컴포넌트로 이어지므로 무시합니다.
첫 번째 예제에서 3은 {4, 3}을 꺼내고, 0은 {2, 1, 0}을 꺼냅니다. 노드 5의 간선은 이미 꺼낸 4로 이어지므로 5만 꺼냅니다.
알고리즘
- 방문하지 않은 각 노드에 다음 인덱스를 부여하고,
low를 같은 값으로 설정한 뒤 노드 스택에 넣고 프레임(node, first edge)을 푸시합니다. - 최상위 프레임의 노드에 아직 남은 간선이 있으면 이를 따라갑니다. 방문하지 않은 대상 노드에는 인덱스와 프레임을 부여하고, 노드 스택에 있는 대상 노드라면
low[node]를 해당 노드의 인덱스로 낮춥니다. - 그렇지 않으면 프레임을 팝하고 부모의
low를low[node]로 낮춥니다.low[node]가index[node]와 같으면 노드 스택에서 해당 노드까지 팝하고 하나의 컴포넌트로 셉니다.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
함정과 경계 사례
- 간선이 없는 노드를 빠뜨리는 것. 두 번째 예시에서는 노드 4가 어떤 간선에도 나타나지 않지만 여전히 구성 요소입니다.
- 스택에 있는 노드만이 아니라 방문한 모든 노드를 통해
low를 낮추는 것. 첫 번째 예시에서는 간선5 → 4때문에 5가 자신의 구성 요소를 닫지 못하게 됩니다. - 간선을 양방향으로 취급하는 것. 이렇게 하면 연결 요소를 세게 됩니다. 첫 번째 예시의 결과는 3이 아니라 1이 됩니다.
- Python에서 재귀를 사용하는 것. 노드 5000개를 거치는 사이클은 호출 5000개를 중첩시키며, 이는 기본 한도인 1000의 다섯 배입니다. 프레임 스택을 직접 관리하세요.
- Kosaraju 알고리즘의 두 번째 패스를 원래 간선에 대해 실행하거나, 노드를 처음 방문한 순서대로 실행하는 것. 두 방법 모두 한 방향으로만 서로 도달할 수 있는 구성 요소를 합쳐 버립니다.
자주 묻는 질문3
강하게 연결된 구성 요소를 찾는 시간 복잡도는 얼마인가요?
Kosaraju 알고리즘이나 Tarjan 알고리즘을 사용하면 모든 노드와 간선이 상수 횟수만큼 처리되므로 시간 복잡도는 O(n + E)입니다. 두 알고리즘 모두 간선 목록과 탐색 스택에 O(n + E)의 공간을 사용합니다.
Kosaraju 알고리즘과 Tarjan 알고리즘 중 무엇을 사용해야 할까요?
Kosaraju 알고리즘은 단순한 탐색 두 번으로 이루어져 있어 잘못 구현하기가 더 어렵습니다. Tarjan 알고리즘은 low를 추적해야 하는 대신 탐색 한 번만 필요하고 역방향 그래프도 필요하지 않습니다.
강하게 연결된 구성 요소와 연결된 구성 요소의 차이는 무엇인가요?
연결 요소는 간선의 방향을 무시합니다. 어떤 경로가 두 노드를 연결하면 두 노드는 같은 요소에 속합니다. 강한 연결 요소에서는 각 노드가 서로에게 도달할 수 있어야 합니다. 첫 번째 예시는 연결 요소 하나이지만 강한 연결 요소는 세 개입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def countSCC(n, edges):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자들
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
예상 출력
3