딥러닝 공부방

2150번 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 문제 풀이 import sys sys.setrecursionlimit(10**6) V, E = map(int, input().split()) visited = [0] * (V+1) # visitied 초기화 graph = [[] for i in range(V + 1)] # 빈 ..

코사라주 알고리즘(kosaraju's algorithm) dfs를 활용하여 그래프 내의 ssc를 찾는 알고리즘 시간 복잡도 O(V+E) 정방향 그래프에서 dfs를 실행하여 post가 높은 정점이 sCc의 source가 되고, 역방향 그래프에서 dfs를 실행하여 post가 높은 정점이 scc의 sink가 된다. 찾은 source와 sink를 묶어 scc를 생성한다. 작동 원리 (1) 방향 그래프 내에서 dfs를 실행하여, dfs 탐색을 마친 정점을 stack에 삽입한다. (2) 역방향 그래프를 생성한다. (3) stack에서 정점을 추출하여, 역방향 그래프에서 dfs를 실행한다. (4) 방문하는 정점을 scc 에 삽입한다. (5) 탐색이 종료되면, scc (6) stack에서 방문하지 않은 정점을 추출하여..