Algorithm/그래프
tarjan's SCC algorithm
jhg0406
2020. 1. 20. 05:31
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
|
//타잔의 강결합 컴포넌트 분리 알고리즘
#include<vector>
#include<stack>
using namespace std;
//그래프의 인접 리스트 표현
vector<vector<int>> adj;
//각 정점의 컴포넌트 번호, 컴포넌트 번호는 0부터 시작하며,
//같은 강결합 컴포넌트에 속한 정점들의 컴포넌트 번호가 같다.
vector<int> sccId;
//각 정점의 발견 순서
vector<int> discovered;
//정점의 번호를 담는 스택
stack<int> st;
int sccCounter, vertexCounter;
//here를 루트로 하는 서브트리에서 역방향 간선이나 교차 간서을
//통해 갈 수 있는 정점 중 최소 발견 순서를 반환한다.
//(어미 SCC로 묶인 정점으로 연결된 교차 간선은 무시한다)
int scc(int here)
{
int ret = discovered[here] = vertexCounter++;
//스택에 here를 넣는다. here의 후손들은 모두 스택에서 here후에 들어간다.
st.push(here);
for(int i = 0; i<adj[here].size(); ++i)
{
int there=adj[here][i];
//(here, there)가 트리 간선
if(discovered[there] == -1)
ret = min(ret, scc(there));
//there가 무시해야 하는 교차 간선이 아니라면
else if(sccId[there] == -1)
ret = min(ret, discovered[there]);
}
//here에서 부모로 올라가는 간선을 끊어야 할지 확인한다.
if(ret == discovered[here])
{
//here를 루트로 하는 서브트리에 남아 있는 정점들을 전부 하나의 컴포넌트로 묶는다.
while(true)
{
int t = st.top();
st.pop();
sccId[t] = sccCounter;
if(t == here) break;
}
++sccCounter;
}
return ret;
}
//tarjan의 SCC알고리즘
vector<int> tarjanSCC()
{
//배열들을 전부 초기화
sccId = discovered = vector<int>(adj.size(), -1);
//카운터 초기화
sccCounter = vertexCounter = 0;
for(int i = 0; i<adj.size(); i++) if(discovered[i] == -1) scc(i);
return sccId;
}
|
|
tarjan's SCC algorithm
SCC 분리 알고리즘
시간복잡도
O(|V| + |E|)
프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2