시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 370 | 133 | 97 | 35.662% |
철민이는 종강을 기념하여 $ N $개의 나라로 즉흥 여행을 떠나기로 했다.
철민이의 조사에 따르면, $ N $개의 나라 사이에는 총 $ M $개의 항공편이 있으며, 각각의 항공편은 출발하는 나라와 도착하는 나라가 정해져있다.
철민이는 즉흥 여행인 만큼 여행 계획을 짜는 대신, 아래 방식으로 여행하겠다는 계획만 세웠다.
위 계획을 본 당신은 철민이가 $ N $개의 나라를 모두 여행할 수 있을지 걱정이 되기 시작했고, 모든 나라를 방문할 수 있는 시작점들을 미리 찾아서 알려주기로 계획했다.
첫째 줄에 나라의 개수 $ N $과 항공편의 개수 $ M $이 주어진다. $( 1 \le N \le 200\,000; $ $ 0 \le M \le 500\,000 )$
둘째 줄부터 $ M $개의 줄에 걸쳐 항공편의 정보가 두 정수 $ v $ $ w $로 주어진다. 이는 $ v $번 나라에서 출발해 $ w $번 나라로 가는 항공편을 의미한다. $( 1 \le v, w \le N; $ $ v \neq w )$
첫째 줄에 모든 나라를 방문할 수 있는 시작점의 개수 $ K $를 출력한다.
이어 둘째 줄에 가능한 시작점들을 오름차순으로 출력한다.
4 5 1 2 2 3 3 1 1 4 4 1
4 1 2 3 4
무슨 시작점을 선택하든 모든 정점을 방문할 수 있는 경로를 찾을 수 있다. 아래는 가능한 경로 중 하나이다.
4 4 1 2 2 3 3 4 4 2
1 1
1번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재한다. 하지만, 다른 정점에서는 모든 정점을 방문할 수 있는 경로가 존재하지 않는다.
4 4 1 2 2 1 3 4 4 3
0
4 3 1 2 2 3 2 4
0
University > 한양대학교 > 제9회 한양대학교 프로그래밍 경시대회 > Advanced Division D번