[절단선과 절단점] Articulation point, Bridge (Cut vertex, cut edge)

절단점/단절점(Articulation point / Cut vertex)

 

절단점이란 무향 그래프에서 해당 점과 인접한 간선들을 모두 지웠을 때 그래프가 두 개 이상의 컴포넌트(서브 그래프)로 나뉘는 정점을 의미한다.

 

해설 게시글

[백준] No.11266 - 단절점 (C++, Articulation point)

 

 

절단선/단절선 (Bridge / Cut edge)

 

절단선이란 무향 그래프에서 간선을 지웠을 때 그래프가 두 개 이상의 컴포넌트로 나뉘는 간선을 의미한다.

절단점을 먼저 공부하고 보면 쉽게 풀 수 있다.

 

해설 게시글

[백준] No.11400 - 단절선 (C++, Bridge)