방향 오일러 경로
플래티넘 IV의견: 0
정점 \(N\)개, 간선 \(M\)개의 방향 다중 그래프가 주어진다. 모든 간선을 정확히 한 번씩 지나는 오일러 경로 또는 회로가 존재하는지 판정한다(시작점과 끝점이 달라도 된다).
존재하면 간선의 수 \(M\)을, 존재하지 않으면 -1을 출력하라. 간선이 없으면 0을 출력한다.
(조건: 차이 \(d(v)=\text{진출}-\text{진입}\) 이 모든 정점에서 0이거나, 정확히 한 정점에서 \(+1\), 다른 한 정점에서 \(-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을 출력한다.
4 3
1 2
2 3
3 4
31→2→3→4. 정점1은 +1, 정점4는 -1, 나머지 0이고 약연결 → 오일러 경로 존재, 간선 3개 → 3.
3 3
1 2
2 1
1 3
31→2, 2→1, 1→3. 정점1: 진출2·진입1(+1), 정점3: 진입1(-1), 정점2: 균형. 오일러 경로 존재 → 3.
riseoj 작성
출처 Original
평가 및 의견
방향 오일러 경로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
방향 오일러 경로