개념
강한 연결 요소란? (Strongly Connected Component (SCC))
노드들이 서로 자유롭게 이동 가능한 모음집이다.
하나의 그래프에서 여러 개의 SCC가 존재할 수 있고, 같은 SCC 내에서는 어느 두 노드를 선택하더라도 한 노드에서 다른 한 노드로 이동이 가능해야 한다.
그림에서의 그래프에는 3개의 SCC가 존재한다.
a, b가 같은 SCC에 존재한다.
이 말은, a에서 b로 이동이 가능하며, b에서 a로 이동이 가능하다는 뜻이다.
b, f는 다른 SCC에 존재한다.
b에서 f로 갈 수 있지만 f에서 b로 갈 방법은 없다.
특징
무향 그래프면 당연히 서로 왕래가 가능할 것이다.
유향 그래프, 즉 방향이 존재하는 간선으로 이루어진 그래프가 SCC를 갖게 된다.
시간 복잡도 O(V+E)를 가진다.
알고리즘 구현
dfs를 활용함.
- 코사라주 알고리즘
- 타잔 알고리즘
타잔 알고리즘
각 노드 모두 부모 노드를 갖는다.
노드에 도착하게 되면 스택에 본인 노드를 넣어준다. 그리고 처음엔 부모 노드를 본인 번호로 설정한다. 이후 dfs로 인접 노드를 탐색하면서 부모 노드를 최대한 작은 수로 업데이트 한다.
- SCC로 판정되는 상황
- SCC로 판정되지 않는 상황
코드
구현 코드에는 id값이 추가되어 사용된다.
위의 예시는 친절하게 탐색 순서대로 노드 번호를 부여했지만, 실제 상황은 그렇지 않다.
부모를 다른 노드의 부모와 계속 비교하며 최솟값 부모를 취해야하는데 실제 노드의 크기가 들쑥날쑥하면 안된다.
따라서 id라는 고유 번호를 도입함으로써 우리가 탐색하는 순서대로 고유값 id를 갖도록 하는 것이다.
부모 번호를 서로 비교할 땐 무조건 이 id를 사용한다. 대신 스택에 넣고 빼는 값들은 노드의 실제 값이어야 한다.
노드 개수와 간선 개수를 입력하고
a에서 b로 가는 간선처럼 a b 형태로 입력한다.
import collections
v, e = map(int, input().split())
graph = collections.defaultdict(list)
for _ in range(e):
a, b = map(int, input().split())
graph[a-1].append(b-1) #0부터 시작하기 위해 -1을 해주어 잠시 인덱스로 변환
d = [-1 for _ in range(v)]
stack=[]
on_stack=[False for _ in range(v)]
id=0
def dfs(cur):
global id
id +=1
d[cur] = id
stack.append(cur)
on_stack[cur] = True
parent = d[cur]
for next in graph[cur]:
if d[next]==-1: #방문 이력이 없는 노드
parent= min(parent, dfs(next))
elif on_stack[next]: #방문 체크는 되어있지만 아직 처리 완료 X
parent = min(parent, d[next])
if parent == d[cur]: #자신과 부모가 동일
scc = []
while True:
node = stack.pop()
on_stack[node] = False
scc.append(node+1) #인덱스를 다시 숫자로 변환
if cur == node:
break
print("Strongly Connected Component", *scc)
return parent
for i in range(v):
if d[i] ==-1: #방문 이력이 없는 노드
dfs(i)
