정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A->B가 된다. www.acmicpc.net 1. 풀이 단절점 알고리즘과 매우 유사. dfs ordering을 하면서, 자신과 자신의 자손들이 갈 수 있는 가장 작은 order가 자신이라면, 그 점 + 그 점의 자손들은 하나의 SCC를 이룬다. 물론 모든 자..