11266

[백준 11266] 단절점 C++

11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net Cut vertex, DFS 1. 문제 해결 아이디어 dfs를 통해서 정점들의 방문순서를 기록해주는게 핵심이다. 현재 노드의 자식중에서 자신보다 더 빠른 방문순서를 가진 정점을 방문하지 않은 자식이 하나라도 있다면 현재 노드는 단절점이 된다. 단절점을 구할 때 중요한 점은 root정점이 단절점인 경우는 따로 구해줘야 하는 것이다. root정점이 자식을 둘 이상 가지고, 자식간에 연결되어있지 않다면 root정점도 Cut vertex가 된..