BOJ11266 (1) 썸네일형 리스트형 단절점 얼마 전에 후배에게 단절점과 SCC에 대한 질문을 받았는데 공부한지 오래되기도 했고 정리하는 시간이 필요할 거 같아서 글로 남기기로 하였다! 단절점은 우선 무향 그래프(Undirected Graph)에서 정의되는 개념이다. 단절점이란, 해당 정점을 그래프에서 지웠을 때 그래프의 전체 컴포넌트 수가 늘어나는 정점을 의미한다. 더 쉽고 풀어서 말해보자면 이쪽과 저쪽을 (혹은 그 이상을) 연결하는 점을 의미한다. 연결성을 중요하게 생각하는 상황에서(라우터의 연결을 나타낸 그래프 같은 거?) 단절점은 정말 중요한 점이다. 해당 정점에 (더 자세하게는 단절점에 연결된 간선이) 문제가 생긴다면 전체적인 연결 자체에 문제가 생긴다는 말이니까. 그렇다면 이 단절점은 어떻게 구할까? 제일 쉽고, 제일 빨리 생각나는 방법.. 이전 1 다음