컴퓨터망을 그래프 모델로 나타낼 수 있다.

즉, 컴퓨터는 그래프의 정점으로 컴퓨터간의 통신선은 에지로 나타낸다.

컴퓨터끼리 통신을 하기 위해서는 메시지가 통신선과 컴퓨터 등을 통하여 원하는 컴퓨터로 가야 한다.

그러나 통신선과 컴퓨터는 고장이 날 수 있으므로 신뢰성이 높은 컴퓨터 망을 구축한다.

다음 그림 (a)에서 컴퓨터 B가 고장이 나게 되면 컴퓨터 A와 C 는 서로 통신이 불가능하게 되지만

(b)에서는 B가 고장 나더라도 컴퓨터 A와 C는 다른 경로를 통해 통신이 가능하므로

(b) 컴퓨터 망이 더 신뢰도가 높다고 할 수 있다.

따라서 우리는 주어진 컴퓨터 통신망의 신뢰도를 떨어뜨리는 컴퓨터나 통신선을 효율적으로 찾는 것이 중요하다.

주어진 그래프에서 그림 (a)의 B와 같은 컴퓨터가 고장이 나므로

서로 통신이 불가능한 컴퓨터가 생기도록 하는 컴퓨터(절점 : Cut Vertex)를 모두 구하는 효율적인 알고리즘을 작성하라.

이 문제는 통신선의 신뢰도를 100%로 가정한다.

절점 찾기 timer 2초 memory 256MB

절점 찾기 2초 256MB