제설차의 순찰 경로
플래티넘 I의견: 0
도시에 \(N\)개의 교차로가 있고, 이들을 잇는 \(M\)개의 양방향 도로가 있다. 두 교차로 사이에 여러 개의 도로가 있을 수도, 같은 교차로로 돌아오는 도로가 있을 수도 있다.
제설차는 \(S\)번 교차로의 차고에서 출발하여, 모든 도로를 정확히 한 번씩 지나 다시 차고 \(S\)로 돌아와야 한다. 이러한 순찰 경로(오일러 회로)가 존재하면 그 경로를 출력하고, 존재하지 않으면 IMPOSSIBLE을 출력하여라.
\(1 \le N \le 100{,}000\)
\(0 \le M \le 300{,}000\)
\(1 \le a, b \le N\), \(1 \le S \le N\)
첫 줄에 교차로 수 \(N\), 도로 수 \(M\), 출발 교차로 \(S\)가 주어진다.
다음 \(M\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어지며, 교차로 \(a\)와 \(b\)를 잇는 양방향 도로를 의미한다.
오일러 회로가 존재하면, 지나는 교차로를 순서대로 한 줄에 출력한다. 이는 \(M+1\)개의 정수로, 첫 번째와 마지막은 모두 \(S\)여야 하며 연속한 두 정수는 도로로 이어져 있어야 한다. 모든 도로를 정확히 한 번씩 사용하는 어떤 회로든 정답으로 인정된다.
존재하지 않으면 IMPOSSIBLE을 출력한다.
3 3 1
1 2
2 3
3 1
1 2 3 1삼각형 1-2-3. 모든 정점의 차수가 2(짝수)이고 연결되어 있으므로 오일러 회로가 존재한다. 1에서 출발해 1->2->3->1처럼 세 도로를 한 번씩 지나 돌아온다. (출력은 가능한 한 회로이다.)
3 2 1
1 2
2 3
IMPOSSIBLE경로 1-2-3. 정점1과 3의 차수가 1로 홀수이므로 모든 도로를 한 번씩 지나 출발점으로 돌아오는 회로가 존재하지 않는다. IMPOSSIBLE을 출력한다.
플래티넘 IVriseoj 작성
출처 Original
평가 및 의견
제설차의 순찰 경로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
제설차의 순찰 경로