강한 연결 요소1 [백준] 2150: Strongly Connected Component - JAVA https://www.acmicpc.net/problem/2150 풀이SCC는 정점들의 부분집합이며, 그 부분집합에 들어있는 서로 다른 두 정점 u, v에 대해 u에서 v로 가는 경로, v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 간선의 정보가 주어질 때, SCC의 개수와 그 안의 정점들을 출력해야 한다. SCC를 구하는 방법으로 코사라주 알고리즘과 타잔 알고리즘이 있다. - 코사라주 알고리즘 방향 그래프, 역방향 그래프, 스택을 사용하여 SCC를 구한다. 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한다. 1. 방향 그래프의 모든 정점에 대해 dfs를 수행하여 끝나는 순서대로 스택에 삽입한다. 2. 아직 방문하지 않은 정점이 있는 경우 다시 DFS를 수행한다... 2024. 5. 18. 이전 1 다음