[백준][BOJ11266] 단절점
1. 문제 : https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 2. 풀이 : DFS 3. 시간복잡도 : O(V+E) 4. 설명 단절점이란 그 정점을 제거 했을 때, 그래프가 두 개 이상으로 나누어지는 정점을 의미한다. 그림[1]에서 단절점은 1, 3, 4, 6 정점이 해당한다. 시작점(루트)을 1번 정점으로하여 DFS로 스패닝트리를 만들고, 각 정점의 진입 순서를 표기하면 그림[2]와 같다. 그림[2]에서 단절점들의..
Algorithm/Graph
2021. 6. 2. 10:29
