🔥

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

첫 줄에 그래프의 정점의 개수 V(1 ≤ V ≤ 20,000)와 간선의 개수 E(1 ≤ E ≤ 200,000)가 빈 칸을 사이에 두고 순서대로 주어진다.
각 정점에는 1부터 V까지 차례로 번호가 붙어 있다.
둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 출력한다.

예제 1 입력

3 2
1 3
2 3

예제 1 출력

YES

Source

v, e = map(int, input().split())

edge = [[] for _ in range(v + 1)]
color = [0 for _ in range(v + 1)]
flag = True

for i in range(e):
	a, b = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)

def dfs(edge, v, c):
	global flag

	# 이미 방문한 정점을 다시 방문하는 경우
	if(color[v] == c):
		return

	# 이미 다른 색깔이 할당된 정점을 다시 방문하는 경우
	if(color[v] == 3 - c):
		flag = False
		return
	color[v] = c

	for u in edge[v]:
		dfs(edge, u, 3 - c)

for i in range(1, v + 1):
	# 방문하지 않은 정점이면
	if(color[i] == 0):
		dfs(edge, i, 1)

if(flag == True):
	print("YES")
else:
	print("NO")

참고