이분 그래프 판별(dfs, bfs)

문제

이분 그래프란, 아래 그림과 같이 정점을 크게 두 집합으로 나눌 수 있는 그래프를 말한다. 여기서 같은 집합에 속한 정점끼리는 간선이 존재해서는 안된다. 예를 들어, 아래 그래프의 경우 정점을 크게 {1, 4, 5}, {2, 3, 6} 의 두 개의 집합으로 나누게 되면, 같은 집합에 속한 정점 사이에는 간선이 존재하지 않으므로 이분 그래프라고 할 수 있다.

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

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 2 ≤ N ≤ 1,000, N-1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. (1 ≤ a, b ≤ N)

 

출력

주어진 그래프가 이분 그래프이면 Yes, 아니면 No를 출력한다.

 

예제 입력 
6 5
1 2
2 4
3 4
3 5
4 6

예제 출력
Yes

예제 입력
4 5
1 2
1 3
1 4
2 4
3 4

예제 출력
No

 

#코드(DFS)

import sys
 
def isBipartite(x, c):
  # c : 1번 그룹과 -1번 그룹, 0은 아직 방문 안함.
  global myGraph, check, flag
  check[x] = c
    
  for i in range(len(myGraph[x])):
    x2 = myGraph[x][i]
    # 인접한 노드를 이미 방문했고, 
    # 그 노드의 그룹이 현재 노드의 그룹과 같다면 이분 그래프가 아니다.
    if check[x2] != 0 and check[x2] == c:
      flag = False
      return 
    if c == 1: c2 = -1
    else: c2 = 1
    
    if check[x2] == 0:
      isBipartite(x2, c2)
    
 
if __name__ == "__main__":
  flag = True
  check = [0]*1000000
  myGraph = {}
  n, m = map(int, sys.stdin.readline().split())  
  
  for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    
    try : myGraph[a].append(b)
    except : 
      myGraph[a] = list()
      myGraph[a].append(b)
      
    try : myGraph[b].append(a)
    except : 
      myGraph[b] = list()
      myGraph[b].append(a)
      
  isBipartite(1, 1)
  
  if flag == True:
    print('Yes')
  else:
    print('No') 

 

# dfs 복습

## template
import sys
 
def dfs(x, side):
  # dfs : x를 인덱스로 visited의 값을 채워나간다.
  # 0, -1, 1
  global myGraph, visited, flag
  visited[x] = side
  for i in range(len(myGraph[x])):
    x2 = myGraph[x][i]
    if visited[x2]!=0 and visited[x2] == side:
      flag=False
      return
    
    if side==1: side2=-1
    else: side2=1
    
    if visited[x2]==0:
      dfs(x2, side2)
    
 
if __name__ == "__main__":
  input   = sys.stdin.readline
  flag    = True
  n, m    = map(int, input().split())
  myGraph = [[] for _ in range(n+1)]
  visited = [0]*(n+1)
  
  for _ in range(m):
    a, b = map(int, input().split())
    myGraph[a].append(b)
    myGraph[b].append(a)
  
  dfs(1, 1)
  if flag:
    print('Yes')
  else:
    print('No')

 

 

#코드(BFS)

#bfs 작동 원리
#(1) 동일한 level에 존재하는 정점을 같은 그룹으로 지정합니다.
#(2) 이미 방문한 정점인 경우, 현재 정점과의 그룹과 비교하여 동일한 그룹이면 False를 반환합니다.
import sys
import collections
 
if __name__ == "__main__": 
  bipatite = True
  V, E     = map(int, sys.stdin.readline().split())
  graph  = [[] for i in range(V+1)] # 빈 그래프 생성
  visited  = [0] * (V+1) # 방문한 정점 체크
    
  for _ in range(E):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b) # 무방향 그래프
    graph[b].append(a) # 무방향 그래프 
    
  q = collections.deque()
  group = 1
  bipatite = True 
  for i in range(1, V+1):
    if visited[i] == 0: # 방문하지 않은 정점이면 bfs 수행
      q.append(i)
      visited[i] = group
      while q:
        v = q.popleft()
        for w in graph[v]:
          if visited[w] == 0: # 방문하지 않은 정점이면 큐에 삽입
            q.append(w)
            visited[w] = -1 * visited[v] # 현재 노드와 다른 그룹 지정
          elif visited[v] == visited[w]: # 이미 방문한 경우, 동일한 그룹에 속하면 False
            bipatite = False
           
  print('Yes' if bipatite else 'No')  

# BFS(복습)

import sys
from collections import deque
 
def bfs():
  global N, M, myGraph
  
  flag    = True
  visited = [-1]*(N+1)
  deq     = deque()
  deq.append((1, True))
  visited[1]=True
  
  while deq:
    x, side = deq.popleft()
   side    = not side
    for i in myGraph[x]:
      if visited[i]==-1:
        visited[i] = side
        deq.append((i, side))
      if visited[x] == visited[i]:
        flag = False
         
  if flag:
    print('Yes')
  else:
    print('No')
        
  
 
if __name__ == "__main__":
  
  input = sys.stdin.readline
  
  N, M    = map(int, input().split()) 
  myGraph = [[] for _ in range(N+1)]
  
  for _ in range(M):
    a, b = map(int, input().split())
    
    myGraph[a].append(b)
    myGraph[b].append(a)
  
  bfs()