그냥 하는 노트와 메모장

해당 게시글은 아래 속성에 맞춰 작성되어있습니다 :) * 무향 그래프(양방향 그래프, Undirected graph) * Cut vertex(절단점, 단절점) 절단점이란 이 점과 이어진 모든 간선을 지웠을 때 두 개 이상의 Component로 나뉘어 지는 정점을 말한다. 역방향 간선을 이용하여 DFS 한 번만에 절단점을 찾을 수 있다. DFS를 통해 DFS spanning tree를 구성하면 정점 u는 아래처럼 분류할 수 있다. 1. u가 root다 2. u가 root가 아니다. 1. u가 root다 정점 u가 root인 경우, 자식의 개수에 따라 절단점이 될 수도 있고 아닐 수도 있다. 자식이 없는 경우는 당연하고, 하나인 경우에도 root가 사라진다고 두 개의 Component로 나눠지는 것은 아니기..