1707_이분그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

 

 

이전에 그래프를 사용했다면 응용해서 풀면 된다.

 

결국 말은 어렵지만, 단순하게 생각해보자.

 

1,2,3번 3개의 점만 있다고 생각해보고 우리는 이를 빨강팀과 파랑팀으로 나눌 것이다.

 

1번과 2번이 연결되어있다면 1,2번은 무조건 다른팀이어야 한다. 즉, 1번이 빨강팀이라면 2번은 파랑팀이어야 한다. 그 후에 만약 2번이 3번과 연결되어 있다면 3번은 빨강팀이 될 수 밖에없다. 이런상황에서 1번과 3번이 연결되어있다면 둘은 다른팀이 될 수 없으므로 NO를 출력하면 되는 것이다.

 

import sys
from collections import deque
input = sys.stdin.readline

k = int(input())

def bfs(start):
    q = deque()
    q.append(start)
    if visited[start] ==0:
        visited[start] = 1
    while q:
        v = q.popleft()

        color = visited[v]
        for i in graph[v]:
            if visited[i] ==0:
                q.append(i)
                if color == 1:
                    visited[i] = 2
                else:
                    visited[i] = 1
            elif visited[i] == color:
                print('NO')
                return
    return True

for _ in range(k):

    v,e = map(int,input().split())
    graph = [[] for __ in range(v+1)]
    visited = [0] * (v+1)

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

    for k in range(1,v+1):
        if not bfs(k):
            break
    else:
        print('YES')

 

 

또 놓치지 않아야하는건 10개의 점이 있다면 10개의 점을 모두 테스트해봐야한다는 것이다!