DAMPER's blog

무향 그래프에서 단절점(Cut vertex) 찾기 단절점이란 해당 정점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두 개 이상으로 나뉘어지는 정점을 말합니다. 아래 그림을 예시로 들었을 때, 1번 정점과 인접한 간선을 모두 지웠을 때, 0번 정점이 떨어져나가 하나의 컴포넌트가 됩니다. 그러므로 1번 정점은 단절점입니다. 마찬가지 이유로 3번, 5번 정점도 단절점입니다. 단절점을 찾는 방법으로 여러가지가 있지만 DFS 탐색 1회만으로 그래프의 모든 단절점을 찾을 수 있습니다. 먼저 아무 정점으로부터 DFS 트리를 만듭니다. 이 때 임의의 정점 u와 연결된 정점들은 모두 u의 조상이거나 자손입니다. 만약 u와 인접한 간선들을 모두 지웠을 때 그래프가 나눠지지 않는 경우는 u의 자손들이 u의 선조와 역..