SCC를 구하는 알고리즘 중 Kosaraju’s Algorithm을 알아봅시다.

SCC는 Strongly Connected Component의 약자로, 강한 연결 요소를 의미합니다.
어떤 강한 연결 요소 안에 있는 정점은, 서로 이동이 가능합니다. 다시 말해, 같은 강한 연결 요소에 있다면, 갈 수 있음을 의미합니다. 방향 그래프에서 정의됩니다.
SCC알고리즘은 그래프를 Strongly Conneted한 서브 그래프로 나누는 알고리즘입니다.

오일러 회로란?

오일러 회로란, 그래프의 모든 간선을 한 번씩만 통과해서, 시작점으로 돌아오는 사이클을 말합니다. 한붓 그리기와 유사한 개념입니다.
오일러 회로가 되기 위해서는 그래프가 단 하나의 컴포넌트로 구성이 되어있어야 하며, 모든 정점의 차수는 짝수가 되어야 합니다.
만약 차수가 홀수인 정점이 두 개 있다면, 오일러 경로를 구할 수 있습니다.

그래프와 관련된 심화 알고리즘을 알아보기 전에, 그래프의 간선을 몇 가지의 종류로 구분하는 방법을 알아봅시다.

문제 링크

• http://icpc.me/13262

문제 링크

• http://icpc.me/13261

서론

Divide and Conquer Optimization은 점화식이 아래 조건을 만족할 때 사용할 수 있습니다.

• 점화식 꼴 : $\displaystyle D(t, i) = min_{1 ≤ j < n}{D(t-1, j)+C(j, i)}$
• 조건 : $D(t, i) = D(t-1, j) + C(j, i)$을 만족하는 가장 작은 $j$를 $P(t, i)$이라고 할 때 $P(t, i) ≤ P(t, i+1)$을 만족

문제 링크

• http://icpc.me/13260

문제 링크

• http://icpc.me/13974

문제 링크

• http://icpc.me/11066