강한 연결 요소 (SCC)

위와 같은 그래프가 있다라 해보자

위에서 강한 연결 요소를 찾아보면

아래 처럼 찾을 수 있다.

첫번째 정점에서 두번째 정점으로 간뒤 다시 첫번째 정점으로 돌아올수있으면 강한 연결 요소다.

위에서 2에서 3으로 이동한뒤 3 -> 4 -> 2 이렇게 이동할수있다.

5에서 6으로 이동하고 6 -> 5로 이동할 수 있으니 5, 6도 강한 연결 요소다.

 

그렇다면

위에서는 강한 연결 요소가 어떻게 될까?

1,2 | 2,3 이 아닌 1, 2, 3 이 강한 연결 요소다.

강한 연결 요소는 가능한 최대의 크기여야한다.

 

이제 위의 그래프에서 강한 연결 요소를 구하는 과정을 살펴보자.

먼저 배열들을 준비해줄거다.

dfsn은 각 정점의 번호를 저장한다. 위의 그래프는 숫자로 이루어져 있지만 숫자가 아닌 ABC같은 경우도 있을 수 있으니 깊이 우선 탐색을 하는 도중마다 숫자를 채워준다. 그와 동시에 이 정점을 이전에 방문한적이 있는지도 알 수 있다.

 

sn은 SCC Number의 줄임말이다. 모든 강한 연결 요소는 각자의 번호를 갖게 될것이다.

위의 그래프에서 1 | 2, 3, 4 | 5, 6 | 7 이렇게 강한 연결 요소가 나뉘었는데 각자에 번호를 붙여

1번 강한연결요소는 1

2번 강한연결요소는 2, 3, 4

3번 강한연결요소는 5, 6

4번 강한연결요소는 7

이렇게 번호로 알 수 있게 해준다.

 

finished는 해당 정점이 강한 연결 요소 로 만들어졌는지를 알려준다.

finished[5] = false라면 아직 강한 연결 요소가 되지 않았다는 뜻이고

finished[1] = true라면 강한 연결 요소가 되었다는 뜻이다.

 

stack은 dfs를 하며 방문한 정점들을 순서대로 담을것이다.

위의 그래프대로라면 1부터 순회할 것이니 1, 2, 3, 4, 5, 6, 7 이렇게 들어갈 것이다.

 

앞으로 한 정점에 도달하면 실행할 행동들이다.

1. dfsn을 채운다. 위의 경우 dfsn[1] 에 1이 들어갈 것이다.

2. stack에 넣는다. stack안에 1이 들어갈것이다.

3. 해당 정점의 조상 정점을 찾는다. 찾는 방법은 좀 있다 나온다.

4. 만약 해당정점의 번호와 조상정점의 번호가 같다면, 즉 자신이 다른 정점들의 조상이라면 강한연결요소를 만든다.

 

지금은 위의 글이 이해가 가지 않을 것이다.

일단 진행해보자.

 

우리는 지금 dfs(1) 실행해 1번 정점부터 깊이 우선 탐색을 돌릴것이다.

먼저 dfsn 배열에 현재 정점 번호를 넣어준다. 현재 정점 번호는 cnt이다. 현재 cnt가 1이니 dfsn에 1을 넣어준다.

 

dfsn에 정점 번호를 넣은 다음에는 cnt값을 1 올려준다. 그래야 다음 정점 번호가 현재 정점번호와 겹치지 않는다.

이제 stack에 정점을 넣어준다. 중요한건 정점의 번호를 넣어주는게 아니라 정점을 넣어주는 것이다.

dfs(int now) 이런식으로 함수가 now를 받으면 dfsn[now]를 넣는것이 아닌닌 now를 넣는것이다.

 

stack에 정점을 넣었다. 이제 정점의 조상 정점을 찾을 차례다.

조상 정점을 찾을 때는 두가지를 확인한다. 

1. 자신의 이웃중 방문하지 않은 이웃의 dfs(next)를 가져온다.

2. 방문은 했지만 아직 강한 연결 요소가 되지 않은 곳의 dfsn을 가져온다.

int parent = dfsn[now];
for (int i = 0; i < domino[now].size(); i++) {
    int next = domino[now][i];
    if (dfsn[next] == 0) parent = min(parent, dfs(next));
    else if(!finished[next]) parent = min(parent, dfsn[next]);
}

코드 상으로는 위 처럼 된다.

1. 자신의 이웃중 방문하지 않은 이웃의 dfs(next)를 가져온다.

dfsn은 처음에는 모두 0으로 초기화가 되어있다. 그러니 dfsn[next]가 0이라면 아직 방문하지 않았다는 뜻이다.

dfs(next)와 parent를 비교해 더 작은걸 parent에 넣는다.

 

2. 방문은 했지만 아직 강한 연결 요소가 되지 않은 곳의 dfsn을 가져온다.

위의 그래프에서 보면 정점 4 가 좋은 예시인것 같다.

정점 4의 이웃 정점은 정점 2 이다. 정점2는 당연히 방문되어 있지만 아직 강한 연결 요소는 되어있지 않다.

방문했다는 것은 dfsn이 채워져있다는 의미이다. 바로 dfsn을 가져와준다.

 

결국 이웃에게 또다시 dfs, 즉 깊이 우선 탐색을 실행시키는 것이다.

다시 돌아와서 과정을 진행해보자. 1의 이웃은 2, 5가 있다. 이중 2를 먼저 확인할 것이다.

아직 2는 dfsn이 채워지지 않았다. 즉, 방문되지 않은 정점이다. 바로 dfs를 돌려준다.

이제 위에처럼 업데이트가 된다.

dfsn은 채워지고 stack도 채워졌다. cnt도 올라 3이 되었다.

1. 자신의 이웃중 방문하지 않은 이웃의 dfs(next)를 가져온다.

2. 방문은 했지만 아직 강한 연결 요소가 되지 않은 곳의 dfsn을 가져온다.

현재 2의 이웃인 3은 방문되지 않았다. 그러니 3에 dfs를 돌려준다.

이제 위에처럼 업데이트가 된다.

dfsn은 채워지고 stack도 채워졌다. cnt도 올라 4가 되었다.

1. 자신의 이웃중 방문하지 않은 이웃의 dfs(next)를 가져온다.

2. 방문은 했지만 아직 강한 연결 요소가 되지 않은 곳의 dfsn을 가져온다.

현재 3의 이웃인 4는 방문되지 않았다. 그러니 4에 dfs를 돌려준다.

이제 위에처럼 업데이트가 된다.

dfsn은 채워지고 stack도 채워졌다. cnt도 올라 5가 되었다.

1. 자신의 이웃중 방문하지 않은 이웃의 dfs(next)를 가져온다.

2. 방문은 했지만 아직 강한 연결 요소가 되지 않은 곳의 dfsn을 가져온다.

 

현재 4의 이웃은 2이다. 2는 dfsn이 채워졌기에 방문은 되었지만 finished는 true가 아닌 상태이다.

그렇기에 dfsn만 가져오면 된다. 2의 dfsn은 당연히 2이다. 그러니 2를 반환한다.

 

parent는 dfs의 리턴값이다.

dfs(4) 내부에서 일어나는 일을 보면

int parent = dfsn[now];
for (int i = 0; i < domino[now].size(); i++) {
    int next = domino[now][i];
    if (dfsn[next] == 0) parent = min(parent, dfs(next));
    else if(!finished[next]) parent = min(parent, dfsn[next]);
}

일단 parent에 dfsn[4]가 주어지니 parent = 4 가 된다. 4의 이웃은 2이고 dfsn[2]는 0이 아니니 다음 조건문이 실행된다.

이제 !finished가 실행되니 parent = min(parent, dfsn[next]) 가 실행된다. next는 이웃정점인 2가 되니

parent = min(parent = 4, dfsn[2] = 2) 이고 parent는 2가 된다.

결국 dfs(4)은 2를 반환하게 된다.

이제 천천히 돌아가보자.

dfs(4)는 2를 반환한다.

dfs(3)에서 실행된 코드를 다시 봐보자.

int parent = dfsn[now];
for (int i = 0; i < domino[now].size(); i++) {
    int next = domino[now][i];
    if (dfsn[next] == 0) parent = min(parent, dfs(next));
    else if(!finished[next]) parent = min(parent, dfsn[next]);
}

parent는 dfsn[3]이니 3이 된다.

그후 3의 이웃인 4에서 dfs(4) = 2의 값이 반환되었다.

parent = min(parent, dfs(4)) = min(3, 2) = 2

즉 parent = 2가 되고 dfs(3)은 2를 반환하게 된다.

이제 dfs(2)로 돌아가보자

int parent = dfsn[now];
for (int i = 0; i < domino[now].size(); i++) {
    int next = domino[now][i];
    if (dfsn[next] == 0) parent = min(parent, dfs(next));
    else if(!finished[next]) parent = min(parent, dfsn[next]);
}

dfs(2)에서 parent는 dfs[2]인 2로 초기화된다.

2의 이웃인 3에서 dfs(3) = 2를 반환했다.

parent = min(parent, dfs(3)) = min(2, 2) = 2 즉 parnet는 2이다.

글의 위쪽에 적은 실행할 행동이다. 이제 4번을 작동시킬 차례이다.

2의 정점번호 dfsn[2] 와 조상정점 parent가 서로 같다. 이제 강한 연결 요소를 만들 차례이다.

강한연결요소는 stack에서 빼가며 만들것이다.

vector<int> scc;
while (true) {
    int t = stack.back();
    stack.pop_back();
    scc.push_back(t);
    finished[t] = true;
    sn[t] = SN;
    if (t == now) break;
}
SCC.push_back(scc);
SN++;

다음 코드와 같이 진행되는데 그림으로 봐볼것이다.

먼저 vector<int> scc는 지금 이순간 만드는 강한 연결 요소이다.

지금 만드는 강한 연결 요소인 2, 3, 4가 이 안에 들어갈 것이다.

SCC는 모든 강한 연결 요소를 저장하는 벡터이다. 지금은 중요한게 아니니 여기까지 적어놓겠다.

 

진행과정을 살펴보면 int t에 stack의 마지막 값을 넣는다.

1. 현재 stack의 마지막 값은 4이다. int t = 4가 되고 stack의 마지막 값을 pop한다.

2. 그후 scc, 지금 만드는 강한 연결 요소에 t값을 넣는다. 그후 finished[t] 를 true로 바꾸고 sn[t]에 SN값을 넣는다.

3. 만약 t와 현재 정점의 번호가 같다면 반복문에서 나온다.

이제 그림으로 봐보자.

1. 맨 처음부터 시작하자 먼저 t에 stack의 마지막 값을 넣고 stack의 마지막 값을 pop한다.

2. 그후 scc, 지금 만드는 강한 연결 요소에 t값을 넣는다. 그후 finished[t] 를 true로 바꾸고 sn[t]에 SN값을 넣는다.

sn[4]에 SN값 (SN은 scc number 강한연결요소 번호의 줄임말이다.) 이 들어갔고

finished[4]도 true로 바뀌었다. 이제 4는 강한 연결 요소에 들어간것이다.

scc (현재 만들고 있는 강한연결요소) 에는 t값인 4가 들어갔다.

 

3. 만약 t와 현재 정점의 번호가 같다면 반복문에서 나온다.

현재 정점 번호는 2이고 t는 4이다. 그러니 반복문은 계속된다.

 

이대로 반복문이 지속되면 아래 그림 처럼 진행된다.

현재 t값이 정점의 번호인 2와 같다. 이제 반복문에서 나간다.

            if (t == now) break;
        }
        SCC.push_back(scc);
        SN++;
    }

반복문에서 나간뒤에는 SCC (모든 강한 연결 요소를 담는 벡터)에 scc를 넣고

SN++를 해준다. 다음에 만들어지는 scc는 현재 scc보다 1 높은 scc number를 갖게 된다.

 

위의 과정을 반복하면 모든 강한 연결 요소를 SCC안에 갖을수있다.