방향 오일러 회로
플래티넘 IV의견: 0
정점 \(N\)개, 간선 \(M\)개의 방향 다중 그래프가 주어진다(다중 간선·자기 간선 가능). 모든 간선을 정확히 한 번씩 지나 시작점으로 되돌아오는 오일러 회로가 존재하는지 판정한다.
오일러 회로가 존재하면 사용된 간선의 수(즉 \(M\))를 출력하고, 존재하지 않으면 -1을 출력하라. 간선이 전혀 없는 경우 답은 0이다.
(방향 그래프의 오일러 회로 조건: 간선이 있는 모든 정점에서 진입차수 = 진출차수이고, 간선이 있는 정점들이 하나의 강연결 요소를 이룬다.)
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le u, v \le N\) (자기 간선·다중 간선 허용)
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 방향 간선 \(u\ v\) (다중·자기 간선 가능).
오일러 회로가 존재하면 간선 수를, 아니면 -1을 출력한다.
3 3
1 2
2 3
3 1
3방향 삼각형 1→2→3→1. 모든 정점 진입=진출=1이고 강연결 → 오일러 회로 존재, 간선 3개 → 3.
3 2
1 2
2 3
-11→2→3. 정점1 진출1·진입0, 정점3 진입1·진출0 → 진입≠진출 → 회로 없음 → -1.
플래티넘 Iriseoj 작성
출처 Original
평가 및 의견
방향 오일러 회로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
방향 오일러 회로