https://www.acmicpc.net/problem/1707
1707번: 이분 그래프입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에www.acmicpc.net
뭔 개소린지 모르겠어서 인터넷을 찾아보았다.
이분그래프는
이렇게 빨간색은 빨간색끼리 연걸 x, 검은색은 검은색끼리 연결 x 하는 그래프를 말한다.
인접한 두 점이 같은 색깔이라면, 이분그래프가 아니다.
만일 어디에도 연결되지 않은 점이라면, 이는 빨간, 검정 두개다 될 수 있다.
모든 정점이 서로 연결되지 않았어도, 이분그래프이다.
이 3가지를 생각한다.
dfs든 bfs든 원리는 똑같다.
아직 방문하지 않은 노드를 탐색하면서, (비연결 그래프인 경우도 고려)
방문하지 않았다면, 레벨에 따라 다른색을 칠한다 ex 지금 빨이라면 이 다음레벨은 검, 그다음은 빨 …..
이미 방문한 노드와 연결된다면, 현재노드색==방문한노드색이라면 인접한 정점이 같은색인것이다.
그런경우엔 싹다종료하고 no출력
끝까지했는데 종료조건을 만족못했으면 yes출력
#bfs
import sysinput=sys.stdin.readlinefrom collections import dequedef bfs(node):
global flag s=deque() s.append(node) visited[node]='white'
while s: tmp=s.popleft() color=visited[tmp]
for i in graph[tmp]: if not visited[i]:
visited[i]=['white','black'][color=='white']
s.append(i) else:
if color == visited[i]: flag=True
return for _ in range(int(input())):
v,e=map(int,input().split()) graph=[[]for _ in range(v+1)]
visited=[False for _ in range(v+1)] for _ in range(e):
a,b=map(int,input().split()) graph[a].append(b)
graph[b].append(a) flag=False for i in range(1,v+1):
if not visited[i]: bfs(i) if flag:
break print('NO' if flag else 'YES')#dfs
주의할점: 재귀로푸는거니깐 recursionlimit설정안하면 오류난다.
import syssys.setrecursionlimit(10**6)input=sys.stdin.readline
from collections import dequedef dfs(node,value): global flag
visited[node]=value for i in graph[node]: if not visited[i]:
dfs(i,-value) else: if value==visited[i]:
flag=True if flag: return
for _ in range(int(input())): v,e=map(int,input().split())
graph=[[]for _ in range(v+1)] visited=[False for _ in range(v+1)]
for _ in range(e): a,b=map(int,input().split())
graph[a].append(b) graph[b].append(a) flag=False
for i in range(1,v+1): if not visited[i]: dfs(i,1)
if flag: break
print('NO' if flag else 'YES')