목록Cycle (1)

코린이의 소소한 공부노트

Tarjan's algorithm

1. Problem - 방향 그래프(directed graph)에서 SCC를 찾아보자. - 강한 요소 결합(Strongly Connected Component, SCC)이란 그래프에 있는 노드 중에서 서로 도달이 가능한 노드들의 집합을 말한다. - 쉽게 말하면, 그래프 안에서 사이클을 이루는 노드의 집합이다. - 타잔 알고리즘은 정점에 대해 DFS(깊이 우선 탐색)을 실행하며 SCC를 찾는다. 2. Input 1) int[][] graph - graph[i][j]는 i번 노드에서 j번 노드로 향하는 간선을 뜻한다. 2) static int vertex - 그래프 내에 존재하는 노드의 수를 의미한다. 3. Output 1) SCC의 개수 2) 각 SCC에 속하는 노드의 번호를 출력 4. Example //..
Back-End/Algorithm 2023. 6. 14. 12:58
이전 Prev 1 Next 다음