멍멍멍

Articulation Point : 단절점 앞으로의 논의는 하나의 컴포넌트(connected component)로 구성된 무방향 그래프에 대해서 진행됩니다. 먼저 아래 무방향 그래프에서 단절점(절단점)을 파란색 테두리로 나타내었습니다. 그림을 보고 직관적으로 알 수 있듯이 단절점은 그 정점을 제거했을 때 그래프가 두개 이상으로 나누어지는 정점을 말합니다. 즉 제거했을 때 그래프의 connected component가 증가하는 정점을 말합니다. 그럼 어떻게 이 단절점을 찾을 수 있을까요? 가장 단순하게 생각해보면 점을 하나씩 없애보고 컴포넌트가 둘로 나눠졌는지 조사하는 것입니다. N : 정점의 개수, M : 간선의 개수라 할때 이 방법의 시간 복잡도는 없앨 정점을 선택하는데 N, 그래프 전체를 dfs탐색..