SCC (Strongly Connexted Component)
22 Jun 2021강한 결합 요소란 서로 긴밀하게 연결된 그래프내의 집합을 의미한다. 여기서 긴밀하게 연결되어있다는 것은 서로 도달이 가능하다는 것을 의미한다. 즉, 같은 SCC내에 속하는 모든 두 정점은 서로를 향한 경로가 있다는 것이다. 만약 방향이 없다면 모든 정점은 서로를 향한 경로가 있을 것이기에 방향 그래프에서만 의미가 있다는 것을 알아두자. SCC를 구하는 알고리즘으로는 크게 코사라주와 타잔 알고리즘이 있다.
1. 코사라주 알고리즘
우리는 그래프를 정방향 그래프와 역방향 그래프 2개를 준비할 것이다. 역방향 그래프란 기존 그래프의 간선 방향을 정반대로 만든 그래프이다. 먼저 정방향 그래프에 대해 dfs를 해서 오일러 투어를 실행할 것이다.
오일러 투어란 간단하게 설명하자면 dfs로 그래프를 순회할 때 정점에 대해서 방문할 때 inOrder번호를 부여하고 빠져나올 때 outOrder번호를 부여하는 것을 말한다. 다음 그림을 보면 이해하기 쉬울 것이다.
실제로는 inOrder는 필요하지 않기 때문에 dfs를 빠져나올 때에만 order번호를 부여했다. finish time 순으로 노드를 저장해주는 ft 배열에 order가 작은 노드부터 저장을 시켜주었다.
- DFS Front Function
func dfsF(n: Int) {
check[n] = true
for e in edgeF[n] {
if !check[e] {
dfsF(n: e)
}
}
ft[index] = n
index += 1
}
그 후 outOrder가 큰 순으로 역방향 그래프에서 dfs를 다시 시행시킨다. 앞에서 구한 ft 배열을 끝에서부터 차례대로 방문하면 된다. 이 때 하나의 노드에서 dfs로 방문하는 모든 노드들은 하나의 SCC가 된다. SCC배열은 각 노드별로 몇번째 SCC에 속하는지를 나타내주는 배열이다.
- DFS Back Function
func dfsB(n: Int, scc: Int) {
SCC[n] = scc
for e in edgeB[n] {
if SCC[e] == 0 {
dfsB(n: e, scc: scc)
}
}
}
유의할 것은 dfsF 함수나 dfsB 함수가 한번 실행하면 모든 노드를 방문하는 것이 아니기 때문에 for문으로 아직 방문한 적이 없는 노드를 만날때마다 실행시켜줘야 한다는 것이다.
- main 함수 중 일부
for i in 0..<n {
if !check[i] {
dfsF(n: i)
}
}
//dfsF에서는 check 배열로 방문여부 확인
for i in 0..<n {
let node = ft[n-1-i]
if SCC[node] == 0 {
scc += 1
dfsB(n: node, scc: scc)
}
}
//dfsB에서는 SCC번호가 노드에 부여되어있는지로 확인
위의 그래프에 SCC를 적용하면 다음과 같이 바뀐다.
놀라운 것은 SCC 집합을 하나의 노드로 보면 사이클이 없는 방향 그래프가 생성된다는 것이다. 또한 SCC 집합을 하나의 노드로 보았을 때 위상정렬에서 먼저 오는 노드는 SCC 번호 순으로도 먼저 오게된다. 이를 활용하여 SCC와 위상정렬이 결합된 문제들이 많이 나온다.
이제 코사라주가 만드는 SCC의 유효성에 대해 증명을 할 것이다. 코사라주가 만든 SCC가 유효하려면 번호가 늦게 생성된 SCC에서 먼저 생성된 SCC로 가는 edge가 존재하지 않음을 보이면 된다. 아까 위에서 구한 SCC 그래프에서 설명해보면 SCC3에서 SCC1나 2로 가는 edge가 없어야한다는 소리이다. 그렇다면 두 SCC간에 edge가 존재한다고 하자.
위 그림을 보면 back DFS를 하는 과정에서 SCC2를 먼저 방문할 것이다. 하지만 새롭게 추가된 빨간 간선에 의해 back DFS과정에서 SCC3까지 방문하게 된다. 따라서 SCC3이라는 집합이 존재하지 못하게 되고 가정이 모순이 되어서 SCC3에서 SCC2로 가는 간선은 존재할 수 없다는 결론이 나오게 된다. 이로써 코사라주 알고리즘의 유효성이 증명되었다.
- 코사라주 전체 코드
var edgeF:[[Int]] = []
var edgeB:[[Int]] = []
var check:[Bool] = []
var ft:[Int] = []
var index = 0, scc = 0
var SCC:[Int] = []
func dfsF(n: Int) {
check[n] = true
for e in edgeF[n] {
if !check[e] {
dfsF(n: e)
}
}
ft[index] = n
index += 1
}
func dfsB(n: Int, scc: Int) {
SCC[n] = scc
for e in edgeB[n] {
if SCC[e] == 0 {
dfsB(n: e, scc: scc)
}
}
}
for i in 0..<n {
if !check[i] {
dfsF(n: i)
}
}
for i in 0..<n {
let node = ft[n-1-i]
if SCC[node] == 0 {
scc += 1
dfsB(n: node, scc: scc)
}
}
2. 타잔 알고리즘
이번에는 코사라주와 조금 다른 타잔 알고리즘에 대해 설명하겠다. 핵심 개념은 dfs로 하나씩 정점을 방문하면서 stack에 노드를 집어넣을 것인데 부모라는 정보를 활용해서 SCC를 구한다는 것이다. 다음 그림을 보면서 이해해보자.
먼저 1번 정점부터 순차적으로 dfs를 해서 4번으로 이동한다. 이 때 처음에 모든 정점은 부모로 자기 자신을 가리키도록 한다.
4번에서 2번을 바라봤을때 SCC그룹에 속해있지 않고 방문한 적이 있는 정점이기 때문에 해당 정점의 부모값과 본인의 부모값을 비교해서 더 작은 값을 본인의 부모로 삼아준다.
그 후 더이상 새 경로를 탐색할 수 없으므로 가지고 있던 부모값을 return 한다. 3번 노드는 return 받은 부모값이 본인이 갖고 있는 값보다 작으므로 부모값을 2로 바꿔준다.
3번은 추가적인 경로가 존재하므로 경로를 타고 들어가 7번 정점까지 방문한다.
7에서 5를 바라봤을때 위와 동일하게 부모값을 변경하고 반환해준다. 그 결과 5까지 돌아가게 되는데 5는 부모값과 본인이 동일하기 때문에 스택에서 본인이 나올때까지 pop해준다.
5, 6, 7이 하나의 그룹이 되고 마찬가지로 3에서 2로 돌아간다. 2도 부모와 본인이 동일하기 때문에 stack에서 pop해준다.
2, 3, 4가 하나의 그룹이 되고 마찬가지로 1도 동일하게 처리해준다.
최종적으로 코사라주와 동일한 SCC 그래프를 얻게된다. 다만 코사라주와 반대로 위상 정렬에서 마지막에 처리해야 할 SCC가 먼저 얻어진다.
유효성을 증명해보자면 코사라주와 동일하게 7 -> 4로 가는 선분이 있다고 생각했을 때 알고리즘을 계산해보면 두 SCC 그룹이 결국에는 하나가 되야하고 서로다른 SCC 그룹이라는 가정에 어긋나기 때문에 타잔의 알고리즘이 유효하다는 것을 증명할 수 있다.
- 타잔 전체 코드
let n = 2000
var edge:[[Int]] = Array(repeating: [], count: n)
var visited:[Int] = Array(repeating: 0, count: n)
var finished:[Bool] = Array(repeating: false, count: n)
var index = 1
var SCC:[[Int]] = []
var NodeSCC:[Int] = Array(repeating: -1, count: n)
var stack:[Int] = []
func dfs(n: Int) -> Int {
visited[n] = index
index += 1
stack.append(n)
var parent = visited[n]
for e in edge[n] {
if visited[e] == 0 {
parent = min(parent, dfs(n: e))
}
else if !finished[e] {
parent = min(parent, visited[e])
}
}
if parent == visited[n] {
var tmpScc:[Int] = []
let count = SCC.count
while !stack.isEmpty {
let tmpNode = stack.popLast()!
tmpScc.append(tmpNode)
finished[tmpNode] = true
NodeSCC[tmpNode] = count
if tmpNode == n {
break
}
}
SCC.append(tmpScc)
}
return parent
}
for i in 0..<n {
if visited[i] == 0 {
dfs(n: i)
}
}
3. 2-SAT
다음과 같은 논리식이 주어진다고 했을 때
f = (x1 V x2) Λ (x1 V ~x2) Λ (~x1 V x3) Λ (~x1 V ~x3)
해당 논리식이 참이되는 해가 존재하는지, 그렇다면 그 해는 무엇인지 구할 때 2-SAT 문제를 푼다고 한다.
여기서 각 원소는 bool 값을 가지며 V는 or를 의미하고 Λ은 and를 의미한다. (x1 V x2)라는 원소의 의미는 전체 식이 참이 되기 위해서 x1이 false라면 x2가 true가 되거나 x2가 false라면 x1이 참이 되어야 함을 의미한다. 따라서 두 x값 간에 선행조건이 생기게 되고 이는 위상정렬 문제로 생각할 수 있다.
false를 표현하기 위해서 우리는 등장하는 모든 xn에 대해 true node와 false node 2개를 생성해준다. 예를 들자면 ~x1 -> x2 로 간선을 긋고 ~x2 -> x1로 간선을 그어준다. 이를 식에 등장하는 모든 관계에 대해 간선을 그어준다.
- 간선 설정 코드
for _ in 0..<m {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
var N1 = line[0], N2 = line[1]
N1 = (N1 < 0 ? -(2*N1) : 2*N1-1)
N2 = (N2 < 0 ? -(2*N2) : 2*N2-1)
edge[makeNot(n: N1)].append(N2)
edge[makeNot(n: N2)].append(N1)
}
//makeNot은 x값에 대해서 다른 부호를 갖는 노드로 바꿔주는 역할을 한다. true -> false / false -> true
그래프를 성공적으로 만들었다면 주어진 논리그래프에 대해 SCC를 구한다. 만약 하나의 SCC에 x1와 ~x1가 모두 속한다고 생각해보자. 그럴 경우 x1은 true도 되야하고 false도 되야한다. 따라서 모든 x값에 대해서 true 노드와 false 노드가 한 SCC에 속하지 않는지를 확인하면 f라는 식을 참으로 만드는 해가 존재하는지 확인할 수 있다.
실제 해를 구하고자 한다면 위상정렬 상에서 앞에 오는 SCC부터 차례대로 그 해를 구하면 된다. 각 x에 대해서 true 노드가 먼저 등장하면 그 해를 false로 false 노드가 먼저오면 x값을 true로 설정한다.
이 부분이 참 중요한데 선행 조건이 없다면 bool식을 false로 만들도록 해야한다. (x1 V x2)라는 조건과 ~x1 -> x2라는 간선을 다시 생각해보자. 이 간선의 의미는 x1이 false가 되버린다면 x2는 무조건 참이여야 한다는 것을 의미한다고 했다.
그렇다면 x1이 true가 되버린다면? x2가 무엇이 오든 아무 문제가 없는 것이다. 따라서 그래프 상에서 선행 조건이 없는 노드를 만난다면 해당 노드를 false가 되도록 설정해주면 뒤에 등장하는 조건식에 아무런 영향을 미치지 않기 때문에 적합한 해를 찾을 수 있다.
- 2-SAT 전체 코드
let n = 20, m = 10
var edge:[[Int]] = Array(repeating: [], count: 2*n)
var visited:[Int] = Array(repeating: 0, count: 2*n)
var finished:[Bool] = Array(repeating: false, count: 2*n)
var NodeSCC:[Int] = Array(repeating: 0, count: 2*n)
var index = 1
var SCC:[[Int]] = []
var stack:[Int] = []
for _ in 0..<m {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
var N1 = line[0], N2 = line[1]
N1 = (N1 < 0 ? -(2*N1)-1 : 2*(N1-1))
N2 = (N2 < 0 ? -(2*N2)-1 : 2*(N2-1))
edge[NotOper(n: N1)].append(N2)
edge[NotOper(n: N2)].append(N1)
}
//조건식 간선 설정 코드
for i in 0..<2*n {
if visited[i] == 0 {
dfs(n: i)
}
}
//SCC생성
var possible = true
for i in 0..<n {
if NodeSCC[2*i] == NodeSCC[2*i+1] {
possible = false
break
}
}
//참이 되는 해 존재 여부 파악
var result = Array(repeating: -1, count: n)
if possible {
for i in 0..<SCC.count {
let currentSCC = SCC[SCC.count-1-i]
for s in currentSCC {
if result[s/2] == -1 {
result[s/2] = s%2
}
}
}
}
//최종 해 계산
func dfs(n: Int) -> Int {
visited[n] = index
index += 1
stack.append(n)
var parent = visited[n]
for e in edge[n] {
if visited[e] == 0 {
parent = min(parent, dfs(n: e))
}
else if !finished[e] {
parent = min(parent, visited[e])
}
}
if parent == visited[n] {
var tmpScc:[Int] = []
let count = SCC.count
while !stack.isEmpty {
let tmpNode = stack.popLast()!
tmpScc.append(tmpNode)
finished[tmpNode] = true
NodeSCC[tmpNode] = count
if tmpNode == n {
break
}
}
SCC.append(tmpScc)
}
return parent
}
func NotOper(n: Int) -> Int {
return (n%2 == 0 ? n+1 : n-1)
}