뭘 기대하고 들어왔는가? 아직 3번 포스팅을 전부 쓰지도 않았다. 굉장히 나태했던것 같긴 한데...조만간 3번 포스팅을 전부 구현하고 작성하고 나면 시작할 것이다.
...라고 하기엔 3번 포스팅을 작성할 엄두가 나질 않는다. 대충 비츠랑 wavelet tree정도가 남았는데 wavelet tree는 이해는 했는데 안짜봤고, 비츠는 음...사실 대충 감은 잡고 있긴 한데 귀찮다. 병렬로 해도 별일 없겠지
억겁의 시간이 지난 9월 2일...비츠는 쓰긴 했고 wavelet tree는 써야 하긴 하는데...wavelet tree에 대한 motivation을 발견하지 못한 채 방황하고 있다. 그래서 그냥 이 글부터 다시 쓰기로 했다.
1. tree에서의 모스 알고리즘
솔직히 이걸 배우고 조금 감회가 새로웠다. 아주 독특하고 신기한 발상이 추가된건 아니지만, 이렇게 typical한 두 알고리즘의 융합으로 이렇게 전역적인 문제를 풀 수 있게 되는게 신기하다. tree 위에서의 모스 알고리즘은 대충 다음과 같은 두 유형의 문제들에 사용이 가능하다:
루트가 있는 트리에서, 어떤 정점이 주어졌을때 해당 정점을 루트로 하는 서브트리에 대해 무언가를 계산하라.
두 정점이 주어졌을 때, 두 정점을 잇는 경로에 대해 무언가를 계산하라.
첫번째 문제의 예시를 들자면, 각 정점마다 가중치가 부여되어 있을 때 한 서브트리 내의 서로다른 가중치의 개수를 구하는 문제같은게 있을 것이다. 이런 문제를 해결할 때 일반적으로 생각할 수 있는 것은, 오일러 투어 테크닉을 적용하여 트리를 펴바르는(?) 것이다. 이렇게 하고 나면, 트리의 구조를 일반적 배열로 생각할 수 있기 때문에 굉장히 쉬워진다. 여기서 알 수 있는 것은, 모스 알고리즘을 이 문제에 적용이 가능하다는 것이다. 즉, ett로 펴바른 배열에서 모스의 아이디어를 적용하면 대충 루트정도로 문제가 풀림을 알 수 있다(하나의 서브트리는 하나의 구간으로 나타나기 때문).
그러나, 두 정점을 잇는 경로에 대한 문제는 쉽사리 풀릴 것 같진 않아보인다...
하지만 사실, 이 역시 오일러 투어 테크닉을 이용하여 다룰 수 있다. 구체적으로, S[x]를 x번 정점에 들어가는 시점, E[x]를 x번 정점에 나가는 시점으로 정의하자. 이제 어떤 쿼리 u,v가 주어지고, 일반성을 잃지 않고 S[u]<S[v]라고 하자. 만약 아-주 나이브하게 [S[u],S[v]]와 같은 구간에 대해 쿼리를 날려주면, 여러번 나오는 정점들 때문에 골머리를 썩힐 것이다. 그러나, 이 경우 우리가 알 수 있는 사실은, 임의의 정점은 한 구간 내에서 2번 이하로 나온다는 것이다(어차피 배열 전체에 한 정점이 두개밖에 없으니까.). 따라서 만약 이미 만났던 정점을 한번 더 만난다면, 해당 정점의 영향을 제거해주는 방식으로 구간을 잘 관리할 수 있다. 다만, 이 경우 두 정점의 LCA가 2번 등장할 가능성도 있으므로, 이것은 따로 예외처리를 해줄 필요가 있다.
물론, 실제로 우리가 사용하는 모스 알고리즘에 비해 트리 위에서의 모스 알고리즘은 그 성능이 제한된다. 예를 들어, 당장 원소들의 순서가 연관된 경우에는 굉장히 해당 알고리즘을 적용하기가 애매해진다는 것을 알 수 있다(모든 순서가 관련된 문제가 안풀린다는 것은 아니다.). 그래도 만약 순서를 무시할 수 있는 경우에는 굉장히 강력한 아이디어가 된다는 사실은 변치 않는다.
간단한 예시로, 13518번: 트리와 쿼리 9 (acmicpc.net)가 아무래도 가장 유명한 예제인 것 같고, 이미 위에서 설명했다. 어떤 구간에서 서로다른 원소의 개수를 출력하는 문제는 굉장한 웰노운이기 때문에 설명은 생략한다.
13518번: 트리와 쿼리 9
N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 정점은 가중치를 가지고
www.acmicpc.net
뭐 내 생각엔 대충 13517번: 트리와 쿼리 8 (acmicpc.net)같은것도 풀 수 있을 것 같긴 한데 음...잘은 모르겠다.
13517번: 트리와 쿼리 8
N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 정점은 가중치를 가지고
www.acmicpc.net
2. 단절점, 단절선
일단, 단절점과 단절선은 많은 사람들이 알고 있을 것이다. 어떤 정점이나 간선을 제거했을 때 컴포넌트 개수가 증가하는 그런 정점이나 간선을 단절점/단절선이라고 한다. 보-통 해외에서는 단절점은 Articulation point라고 하고, 단절선을 bridge 혹은 Articulation bridge라고 하는 것 같다. 관련 자료를 검색할때 참고하자.
아무튼, 일단은 단절선부터 시작해보자. 가장 간단하게 생각해서, 모든 간선들을 제거해보고 이때 컴포넌트의 개수가 늘어나는지 확인해보는 알고리즘이 있을 것이다. 그러나, 이것은 굉장히 비효율적이다...조금 더 빠르게 할 수 있는 방법은 없을까?
정말 다행히도, 단절선의 경우에는 $O(n+m)$만에 단절선을 전부 구할 수 있는 간편한 알고리즘이 있다! 기본적인 아이디어는 그래프에서의 dfs를 함으로써 진행된다. 만약 dfs의 과정에서 정점 v를 보고 있다고 하자. v와 그 자식 p에 대해서, 그 둘을 잇는 간선이 단절선이라면, v의 아래쪽에 있는 그 어떤 정점들도 v의 위쪽에 있는 정점들과 연결되지 않았음을 의미한다. 물론 이러한 방식으로 기술한다면 과도하게 추상적이고 그 의미를 이해하기 어려울 것이므로 조금 더 구체적인 알고리즘을 들고 오겠다.
우선, root에서부터 dfs를 하면서, dfs ordering을 매긴다(dfs[v]와 같이 표기하자). 그리고, 각 정점들 v에 대해서, low[v]를 v가 탐색중일 때 방문하는 모든 정점들과, 혹은 "방문하려 했으나 이미 탐색중이거나 탐색이 완료되어 거절된" 모든 정점들의 dfs ordering의 최솟값으로 정의할 것이다. 다만, 특수하게 바로 직전의 간선으로 연결된 부모정점의 경우에는 무시하자.
이러한 정의하에서, 만약 dfs[v]>=low[p]였다고 생각해보자. 이 사실이 무엇을 의미하는가? 잘 생각해보면, v 이후로 p가 적당한 정점들을 만나면서, 결국은 v보다 더욱 이전에 탐색되었던 어떤 정점을 만났다는 사실을 의미한다. 즉, v-p 직행 간선을 타지 않고도 적당한 경로가 존재해서 그 경로를 따라서 v에 도달 가능하다는 의미이므로, 결국 이는 단절선이 아님을 의미한다. 사실, 이런 논의의 구조를 살펴보면 자명히 이것이 필요충분조건임을 확인이 가능하고, 따라서 dfs[v]<low[p]라면 v와 p를 잇는 간선이 단절선임을 알 수 있는 것이다.
이러한 세팅 하에서, 단절점 또한 굉장히 편리하게 찾아낼 수 있다. 단절선의 경우에는 v에서 p로 또 적당한 경로를 거쳐 v로 다시 도달하는 경우였어도 단절선이 아니었지만, 단절점의 경우에는 그럴 가능성이 있다. 그러나, 결국 단절점도 "v보다 먼저 탐색된 정점"으로 도달하는 경로가 있는 경우에는 v가 단절점이 아니게 된다. 따라서 이런 점을 고려해주면, 단순히 dfs[v]<=low[p]라면 v가 단절점이라고 결론지을 수 있다. 단절선에 비해 그 구현의 차이가 거의 없음을 알 수 있다.
3. 3-edge connectivity
이제 우리는 단절선과 단절점을 구할 수 있게 되었다! 따라서, 우리는 다음과 같은 질문에 답할 수 있다:
주어진 그래프의 어떤 간선을 제거해도 연결된 상태인가?
해당 문제는 단절선의 존재 유무를 묻는 문제로 환원 가능하다. 그렇다면, 이런 질문은 어떨까?
주어진 그래프의 어떤 두 간선을 제거해도 연결된 상태인가?
혹은 조금 더 확장해서, 아예 이런 문제를 생각할수도 있다:
주어진 그래프의 어떤 k개의 간선을 제거해도 연결된 상태인가?
보통 이런 성질을 만족한다면 k+1-edge connectivity라고 한다. 즉, 우리가 다룬 단절선의 존재 여부는 2-edge connectivity에 대한 해답이라 생각할 수 있는 것이다!
다른 문제들은 제쳐두고, 우선 3-edge connectivity부터 분석해보자.
어...일단 방금 3 edge connectivity에 대해 알아보려고 검색을 해봤는데 굉장히 섬뜩한 선형시간 3-edge connectivity에 대한 논문들이 존재하는 것 같다. 게다가 이것 말고 딱히 다른 글도 없는 것 같다... 일단 지금 이 논문을 읽기에는 너무 답이 없어서 던진다.
