[오일러 경로] 백준 16168번: 퍼레이드 / 골드 4

https://www.acmicpc.net/problem/16168

16168번: 퍼레이드

import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

v, e = map(int, input().split())
adj = [0 for i in range(v)]
visited = [False for i in range(v)]
graph = collections.defaultdict(list)

for i in range(e):
    a, b = map(int, input().split())
    adj[a-1] += 1
    adj[b-1] += 1
    graph[a].append(b)
    graph[b].append(a)

def dfs(node):
    for next in graph[node]:
        if not visited[next-1]:
            visited[next-1] = True
            dfs(next)

odd = 0
for i in range(v):
    if adj[i] % 2 == 1:
        odd += 1

if odd == 1 or odd > 2:
    print('NO')

else:
    visited[0] = True
    dfs(1)
    for elem in visited:
        if not elem:
            print('NO')
            quit()
    print('YES')

오일러 경로를 직접 만드는 것보다는 오일러 경로가 가능한 조건이 무엇인지 묻는 문제다.