개념
방향 그래프에서 강한 연결 요소(Strongly Connected Component)란 임의의 두 정점 u, v 사이에 u→v, v→u 경로가 모두 존재하는 최대 부분 그래프이다.
핵심 특징
- 방향 그래프 전용: 무향 그래프에서는 연결 요소(CC)와 동일
- SCC 내부: 어떤 정점에서 다른 어떤 정점으로든 도달 가능
- SCC 축약 (DAG): SCC를 하나의 노드로 축약하면 DAG가 됨
동작 원리 예시
1
2
3
4
5
6
7
8
9
10
| 그래프:
1 → 2 → 3 → 1 (사이클)
3 → 4 → 5
5 → 6 → 4 (사이클)
SCC 1: {1, 2, 3} (1→2→3→1 순환)
SCC 2: {4, 5, 6} (4→5→6→4 순환)
축약 DAG:
SCC1 → SCC2
|
핵심 연산 & 시간복잡도
| 알고리즘 | 시간복잡도 | DFS 횟수 |
|---|
| 타잔 | O(V + E) | 1회 |
| 코사라주 | O(V + E) | 2회 |
타잔 알고리즘
DFS 한 번으로 SCC를 찾는다. 각 정점에 DFS 방문 순서를 부여하고, 도달 가능한 가장 작은 순서 번호를 추적한다.
STL 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <vector>
#include <stack>
#include <algorithm>
const int MAX_V = 100001;
std::vector<int> adj[MAX_V];
int dfsn[MAX_V]; // DFS 방문 순서
int low[MAX_V]; // 도달 가능한 최소 dfsn
bool onStack[MAX_V];
int timer = 0;
std::stack<int> st;
std::vector<std::vector<int>> sccs;
int sccId[MAX_V]; // 각 정점이 속한 SCC 번호
int sccCnt = 0;
void dfs(int cur) {
dfsn[cur] = low[cur] = ++timer;
st.push(cur);
onStack[cur] = true;
for (int next : adj[cur]) {
if (dfsn[next] == 0) {
// 미방문
dfs(next);
low[cur] = std::min(low[cur], low[next]);
} else if (onStack[next]) {
// 스택에 있는 정점 → 같은 SCC 후보
low[cur] = std::min(low[cur], dfsn[next]);
}
}
// cur이 SCC의 루트인 경우
if (low[cur] == dfsn[cur]) {
std::vector<int> scc;
while (true) {
int v = st.top();
st.pop();
onStack[v] = false;
sccId[v] = sccCnt;
scc.push_back(v);
if (v == cur) break;
}
sccs.push_back(scc);
sccCnt++;
}
}
void findSCC(int V) {
for (int i = 1; i <= V; i++) {
if (dfsn[i] == 0) {
dfs(i);
}
}
}
|
코사라주 알고리즘
DFS 두 번으로 SCC를 찾는다. 첫 번째 DFS에서 완료 순서를 기록하고, 역방향 그래프에서 역순으로 두 번째 DFS를 수행한다.
STL 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <vector>
#include <algorithm>
const int MAX_V = 100001;
std::vector<int> adj[MAX_V]; // 원본 그래프
std::vector<int> radj[MAX_V]; // 역방향 그래프
bool visited[MAX_V];
std::vector<int> order; // 완료 순서
int sccId[MAX_V];
int sccCnt = 0;
// 1단계: 원본 그래프에서 DFS, 완료 순서 기록
void dfs1(int cur) {
visited[cur] = true;
for (int next : adj[cur]) {
if (!visited[next]) {
dfs1(next);
}
}
order.push_back(cur); // 후위 순서
}
// 2단계: 역방향 그래프에서 DFS, SCC 할당
void dfs2(int cur) {
sccId[cur] = sccCnt;
for (int next : radj[cur]) {
if (sccId[next] == -1) {
dfs2(next);
}
}
}
void kosaraju(int V) {
// 1단계
std::fill(visited + 1, visited + V + 1, false);
for (int i = 1; i <= V; i++) {
if (!visited[i]) {
dfs1(i);
}
}
// 2단계: 완료 순서의 역순으로
std::fill(sccId + 1, sccId + V + 1, -1);
sccCnt = 0;
for (int i = order.size() - 1; i >= 0; i--) {
int v = order[i];
if (sccId[v] == -1) {
dfs2(v);
sccCnt++;
}
}
}
|
비교 정리
| 특성 | 타잔 | 코사라주 |
|---|
| DFS 횟수 | 1회 | 2회 |
| 역방향 그래프 | 불필요 | 필요 |
| 구현 난이도 | 보통 | 쉬움 |
| SCC 순서 | 역 위상 순서 | 위상 순서 |
| 스택 | 명시적 스택 사용 | 완료 순서 저장 |
사용 예시
2-SAT 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <bits/stdc++.h>
using namespace std;
// 2-SAT: 불리언 변수의 논리식 만족 가능성 판별
// (x ∨ y) 절 → ¬x → y, ¬y → x 두 간선 추가
// SCC에서 x와 ¬x가 같은 SCC에 있으면 UNSATISFIABLE
const int MAX = 200001; // 변수 N개 → 정점 2N개
vector<int> adj[MAX], radj[MAX];
bool visited[MAX];
vector<int> order;
int sccId[MAX];
int sccCnt;
void dfs1(int cur) {
visited[cur] = true;
for (int next : adj[cur])
if (!visited[next]) dfs1(next);
order.push_back(cur);
}
void dfs2(int cur) {
sccId[cur] = sccCnt;
for (int next : radj[cur])
if (sccId[next] == -1) dfs2(next);
}
// 변수 i: true = i, false = i + N
// N개 변수, M개 절
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
// a, b는 1-indexed. 음수면 NOT
int na, nb;
// a가 참: a, 거짓: a+N (1-indexed)
// NOT a: a+N → a, a → a+N
if (a > 0) { na = a + N; a = a; }
else { na = -a; a = -a + N; }
if (b > 0) { nb = b + N; b = b; }
else { nb = -b; b = -b + N; }
// (a ∨ b) → ¬a→b, ¬b→a
adj[na].push_back(b);
radj[b].push_back(na);
adj[nb].push_back(a);
radj[a].push_back(nb);
}
int total = 2 * N;
for (int i = 1; i <= total; i++)
if (!visited[i]) dfs1(i);
fill(sccId + 1, sccId + total + 1, -1);
sccCnt = 0;
for (int i = order.size() - 1; i >= 0; i--) {
if (sccId[order[i]] == -1) {
dfs2(order[i]);
sccCnt++;
}
}
// 판별: x와 ¬x가 같은 SCC면 불가능
for (int i = 1; i <= N; i++) {
if (sccId[i] == sccId[i + N]) {
cout << 0 << '\n';
return 0;
}
}
cout << 1 << '\n';
// 해 구하기: SCC 번호가 큰 쪽이 참
for (int i = 1; i <= N; i++) {
cout << (sccId[i] > sccId[i + N] ? 1 : 0) << ' ';
}
return 0;
}
|
SCC 축약 (DAG 변환)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
using namespace std;
// SCC를 찾은 후 축약 그래프(DAG) 생성
const int MAX_V = 100001;
vector<int> adj[MAX_V];
int sccId[MAX_V];
int sccCnt;
// ... (타잔 or 코사라주로 SCC 계산) ...
// 축약 DAG 생성
vector<int> dag[MAX_V];
void buildDAG(int V) {
set<pair<int, int>> dagEdges;
for (int u = 1; u <= V; u++) {
for (int v : adj[u]) {
if (sccId[u] != sccId[v]) {
dagEdges.insert({sccId[u], sccId[v]});
}
}
}
for (auto [u, v] : dagEdges) {
dag[u].push_back(v);
}
}
|
주의사항 / Edge Cases
단일 정점도 SCC
1
2
| // 자기 자신만으로도 SCC를 형성
// 모든 정점은 반드시 하나의 SCC에 속함
|
타잔에서 low 갱신 주의
1
2
3
4
5
| // 미방문 정점: low[cur] = min(low[cur], low[next])
// 스택에 있는 정점: low[cur] = min(low[cur], dfsn[next])
// 스택에 없는 정점 (이미 SCC 확정): 무시
// 이 구분이 중요! 잘못하면 SCC가 잘못 나뉨
|
재귀 깊이 주의
1
2
3
| // V가 크면 (10만 이상) 재귀 DFS에서 스택 오버플로우 가능
// 리눅스: ulimit -s unlimited
// 또는 명시적 스택으로 변환
|
코사라주에서 역방향 그래프
1
2
3
| // 간선 입력 시 역방향 그래프도 함께 구성
adj[u].push_back(v); // 원본
radj[v].push_back(u); // 역방향
|
면접 포인트
자주 나오는 질문
Q1. SCC란?
- 방향 그래프에서 모든 정점 쌍이 서로 도달 가능한 최대 부분 그래프
- SCC를 하나의 노드로 축약하면 DAG가 됨
Q2. 타잔과 코사라주의 차이는?
- 타잔: DFS 1회, low 값으로 SCC 루트 판별, 스택 사용
- 코사라주: DFS 2회, 완료 순서 + 역방향 그래프
- 둘 다 O(V + E)
Q3. SCC 축약이 DAG가 되는 이유는?
- SCC A → SCC B 간선이 있으면서 B → A 간선도 있다면
- A와 B는 서로 도달 가능 → 하나의 SCC여야 함 (모순)
- 따라서 축약 그래프에 사이클이 없음
Q4. 2-SAT에서 SCC를 사용하는 이유는?
- (a ∨ b) 절을 함의 그래프의 간선 2개로 변환
- 같은 SCC에 x와 ¬x가 있으면 x→¬x→…→x 순환 → 모순
- SCC 순서를 이용해 변수의 참/거짓 결정
Q5. SCC의 활용 예시는?
- 2-SAT 문제
- 도로 네트워크 분석 (상호 도달 가능한 도시 그룹)
- 컴파일러: 순환 의존성 탐지
- 그래프 축약 후 DAG 알고리즘 적용
코드 체크리스트
1
2
3
4
5
6
7
8
9
| // 코사라주
// 1. 원본 + 역방향 그래프 구성
// 2. 원본 DFS → 완료 순서 저장
// 3. 역방향 DFS (완료 순서 역순) → SCC 할당
// 타잔
// 1. dfsn, low 배열 + 스택
// 2. DFS 중 low 갱신
// 3. low[cur] == dfsn[cur]이면 스택에서 SCC 추출
|
추천 문제