#7 SCC, 2_Sat

SCC는 방향 그래프에서 등장하는 개념

SCC는 그래프의 정점의 부분집합들인데, 하나의 SCC안에 있는 어떤 두 정점 u, v를 골라도 u -> v 로 가는 

직간접적인 경로가 존재한다.

SCC는 maximal 한 성질을 가지므로, 크기가 가능한 커야 한다.

초록색 부분(1, 2, 3) , 노란색 부분 (4, 5) 그리고 파란색 부분 (6, 7, 8)은 각각 SCC이다.

 

SCC를 구한다 = 방향 그래프를 SCC로 분리한다.

 

사이클이 없는 방향 그래프는 DAG(Directed Acyclic Graph) 라고 한다.

어떤 방향 그래프에서 SCC로 정점들을 묶어주게 되면, 그래프는 반드시 DAG가 된다.

따라서 사이클이 존재한다면 풀 수 없었던 문제들도, 그래프 자체를 DAG로 바꾸면서 문제를 풀 수 있게된다.

 

시간복잡도 O(V+ E)에 그래프를 SCC로 분리해주는 타잔 알고리즘을 배워보자.

 

타잔 알고리즘은 스택과 DFS를 이용한 알고리즘

우선 그래프를 DFS 스패닝 트리로 표현

DFS를 진행하면서 자신의 자손들이 자신의 조상으로 갈 수 있는 경우가 하나도 없을 경우, 자신을 포함한 

하나의 SCC를 찾은 것이다.

스택에서 자신과 자신위에 있는 정점을 모두 뽑아 하나의 SCC로 판별

위의 그래프를 스패닝 트리 형태로 표현한 것

파란색 간선 : back edge (자신의 조상으로 가는 간선)

검은색 간선 : tree edge (기본적인 트리 간선)

빨간색 간선 : cross edge (아무것도 아닌 간선)

forward edge : 자신의 자손 노드로 가는 간선 (ex 1 -> 4)

 

 

 

 

 

 

 

 

 

 

그래프의 SCC를 구하는 방식에 있어서, forward edge와 cross edge는 무시해도 좋다.

우선 dfs의 각 노드의 방문 순서를 저장해 둘 배열 dfsn[],

SCC추출이 끝났는지 여부 finished[]배열

만들어 준다.

방향 그래프에서 사이클을 판정하는 방법과 유사한 용도로 finished 배열이 사용될 건데, 그때는 방문이 전부 끝났을때, 

finished가 true가 됐다면, 이번에는 특정 정점의 SCC의 추출이 끝났을 때 true가 된다.4

 

자신 포함 자신의 자손들이 자신의 조상으로 갈 수 있는 경우가 하나도 없을 경우 SCC 추출!!

1번 노드 부터 DFS를 진행하면서 탐색해 준다.

5의 DFS가 끝나면 4로 가게 되는데,

4는 자신의 자손들 중 자신의 조상으로 갈 수 없다.

 

따라서 4가 나올 때 까지 Stack에서 뽑고 SCC로 판정

 

 

 

 

 

 

 

8까지 탐색하면 8은 자신 포함 자신의 자손들 중 자신의 조상으로

갈 수 있다.

7 또한 자신 포함 자신의 자손들 중 자신의 조상으로 갈 수 있다.

6은 자신의 조상으로 갈 수 없으므로 6이 나올 때까지 Stack에서 

뽑고 SCC로 판정

 

 

 

 

 

 

 

마지막으로 1이 나올 때 까지 Stack에서 뽑고 SCC로 판정

 

이런 작업을 통해 알 수 있는것은, cross edge를 무시해도 좋은 이유는, 이곳에서 반대쪽 SCC로 가는 간선이 있어도, 

돌아올 수 없기에 무시해도 좋다. forward edge는 SCC판정 과정에 있어서 자신의 자손 전부를 판정해야 하므로 

무시해도 좋다.

시간 복잡도 O(V+E)임을 알 수 있다.

예시문제

백준 2150 (Strongly Connected Component) c++

---

2-sat 문제는 scc를 이용하면 다항시간내에 해결 할 수 있고, 2-sat문제를 통해 여러가지 문제들을 2-sat으로 

치환해서 해결할 수 있다.

예시문제

백준 11280 (2-SAT _3) C++

예시문제

백준 11281(2-SAT_4) C++