[백준/bfs] 1707번: 이분 그래프

-문제: https://www.acmicpc.net/problem/1707

문제의 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프가 이분그래프라고 이해하면 될 것 같다. 

방문하지 않은 노드에 한하여 이전 노드와 다른 색깔(-1 또는 1)을 부여한다

만약 이전노드와 현재 노드가 같은 색인데 현재노드와 이전노드 모두 방문한적이 있다면 False를 반환한다 

 

문제를 input받은 다음에 bfs(i)값이 False라면 'NO'를 출력하고,

아니라면 'YES'를 출력한다

 

queue에 append하는 것도 잊지말자!!

처음에 visit=1값 하는 것도 잊지 말기 

 

 

-정답풀이 :

from collections import deque

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                visit[i]=-visit[x]
                queue.append(i)
            elif visit[i]==visit[x]:
                return False
    return True  

t=int(input())
for _ in range(t):
    v,e=map(int,input().split())
    graph=[[] for _ in range(v+1)]
    visit=[0]*(v+1)
    flag=True
    for _ in range(e):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1,v+1):
        if not visit[i]:
            if not bfs(i):
                flag=False
                break
    if flag:
        print('YES')
    else: 
        print('NO')