문제
컴퓨터망을 그래프 모델로 나타낼 수 있다.
즉, 컴퓨터는 그래프의 정점으로 컴퓨터간의 통신선은 에지로 나타낸다.
컴퓨터끼리 통신을 하기 위해서는 메시지가 통신선과 컴퓨터 등을 통하여 원하는 컴퓨터로 가야 한다.
그러나 통신선과 컴퓨터는 고장이 날 수 있으므로 신뢰성이 높은 컴퓨터 망을 구축한다.
다음 그림 (a)에서 컴퓨터 B가 고장이 나게 되면 컴퓨터 A와 C 는 서로 통신이 불가능하게 되지만
(b)에서는 B가 고장 나더라도 컴퓨터 A와 C는 다른 경로를 통해 통신이 가능하므로
(b) 컴퓨터 망이 더 신뢰도가 높다고 할 수 있다.
따라서 우리는 주어진 컴퓨터 통신망의 신뢰도를 떨어뜨리는 컴퓨터나 통신선을 효율적으로 찾는 것이 중요하다.
주어진 그래프에서 그림 (a)의 B와 같은 컴퓨터가 고장이 나므로
서로 통신이 불가능한 컴퓨터가 생기도록 하는 컴퓨터(절점 : Cut Vertex)를 모두 구하는 효율적인 알고리즘을 작성하라.
이 문제는 통신선의 신뢰도를 100%로 가정한다.
입력
첫 번째 줄에는 컴퓨터 네트워크에 속한 컴퓨터의 수 n과 통신 링크의 수 m이 주어진다. 여기서 n은 300,000 이하의 양의 정수이고 m은 1,000,000이하인 양의 정수이다. 둘 째 줄부터 m개의 줄에 한 줄에 하나씩 통신 링크가 주어진다. 통신 링크는 그것이 잇는 컴퓨터의 쌍으로 중복되어 주어지지 않는다. 입력되는 컴퓨터 네트워크는 분리되어 있지 않고 모두 연결되어 있다.(connected component)
출력
첫째 줄에 절점 노드의 번호를 공백으로 구분하여 노드 번호의 오름차순으로 출력한다. 절점이 존재하지 않는 경우는 -1을 출력한다.
예제1
910
12
28
89
91
23
34
47
37
45
76
2347