[C++] 11266: 단절점

플래티넘 Ⅳ

 

단절점 알고리즘 배운 문제!

 

(코드)

 

어떤 노드 A와 연결되어 있는 노드들을 adj_A 집합 이라고 하면

adj_A 들 중 두 개를 선택했을 때 만약

<이 두 개의 노드가 A를 거치지 않고서 갈 수 있는 경로가 존재하지 않는 경우> 가 하나라도 존재한다면

A는 해당 그래프에서 단절점이라고 할 수 있다

 

-> 따라서! (모든 노드들에 대해서 A라고 가정하고 수행하면 오래 걸리므로)

스패닝 트리를 하나 만들고, 해당 스패닝 트리에서,

A보다 먼저 선택되는 점들을 B 집합(스패닝 트리에서의 부모)이라고 하고

나중에 선택되는 점들을 C 집합(스패닝 트리에서의 자식)이라고 할 때,

<C 집합에 있는 노드 -> B 집합에 있는 노드 의 경로가 존재하지 않는 경우> 가 하나라도 존재한다면

A는 해당 그래프에서 단절점이라고 할 수 있다

 

예외) A가 루트라면, 자식노드가 2개 이상인 경우가 단절점이다