절단점

절단점(Articulation Point) 또는 단절점이라고도 불리며

무향그래프(Undirected Graph)에서 정점 하나를 삭제 했을 때 해당 정점이 포함된 그래프가

두 개 이상의 컴포넌트(component)로 분리되는 정점을 말합니다.

해당 정점이 절단점인지 확인하는 방법으로는 간단하게

그 정점의 자손들이 모두 선조로 가지 않는다면 그 점은 절단점입니다.

DFS를 이용하여 이를 좀 더 쉽게 구현합니다.

정점의 발견 순서를 기록 한 뒤 이 노드에서 갈 수 있는 가장 작은 정점의 번호를 반환하는 함수를 만들어서

한 정점의 자손들의 반환 값이 모두 이 정점의 발견 순서보다 크다면

이 정점의 선조로 가지 않는다는 의미이므로 이 정점은 절단점입니다.

이 때 루트 노드의 경우 이전에 발견한 노드가 없기에 절단점이 아니게 되는데

루트의 자손이 2개 이상일 경우는 루트가 절단점이 될수도 있으므로 예외 조건을 추가하여 구할 수 있습니다.

또한 절단점 확인 알고리즘을 응용하여 절단선(Bridge)을 구할 수도 있으며

이러한 방법이 추후 그래프를 SCC로 분리하기 위해 사용하는 타잔의 알고리즘을 구현하는데 약간의 적용이 되어집니다.

기본 문제

11266번: 단절점

11400번: 단절선