이분 그래프 풀이

문제 링크: https://www.acmicpc.net/problem/1707

백준 알고리즘 기초 2/2 600에서 4번째 - 1707번 이분 그래프를 풀어보았다.

 

풀이: https://ji-gwang.tistory.com/293 를 참고했다.

 

C++

 

Python

import sys
sys.setrecursionlimit(100000)

def dfs(v,a):
	global res
	if res: return
	visit[v]=a
	for i in mat[v]:
		if not visit[i]:
			dfs(i,-a)
		elif visit[v]==visit[i]:
			res=True
			return

k=int(input())
for _ in range(k):
	v,e=map(int,sys.stdin.readline().split())
	mat=[[] for _ in range(v+1)]
	visit=[False]*(v+1)
	for i in range(e):
		a,b=map(int,sys.stdin.readline().split())
		mat[a].append(b)
		mat[b].append(a)
	res=False
	for i in range(1,v+1):
		if not visit[i]:
			dfs(i,1)
			if res: break
	print('NO' if res else 'YES')

Java