BOJ 1707 이분 그래프

https://www.acmicpc.net/problem/1707
시간 2초, 메모리 256MB
input :

• t(2≤t≤5)
• v e (1≤v≤20,000)(1≤e≤200,000)
• a b (인접한 두 정점의 번호가 주어짐)

output :

• 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력

조건 :

• 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)

---

둘로 분할 해서.
분할 한 것 안에서 인접하지 않아야 한다.

graph 기록 해둔 것을 다 돌면 되지 않을 까?
만약
1 4
2 3 4 5
3 2
4 2
5 2
의 인접 리스트가 존재 할 때.
1 / 4 나누고.
2는 4와 같이 있으면 안 되니
1 2 / 4 로 나누고
3 2와 같이 있으면 안 되니
1 2 / 4 3 로 나누고
5 2 와 같이 있으면 안 되니
1 2 / 4 3 5로 나눈다.
중간에 멈추지 않았으니 YES를 출력

예외.
정점이 1개일 때는 언제나 불가능.

처음에 두개의 리스트를 나눠서 in을 이용해서 풀려고 했는데. 계속 O(n)만큼의 반복이 일어나서 인지 시간 초과가 떴다.

다른 분들의 풀이를 보니 리스트를 나누기 보다 score : 1, -1 두개로 나눠서 리스트에 저장을 하는 방식을 이용.

q그러니 BFS를 이용해서 들어간 것이 아닌 경우엔. 다 score ; 1로 저장을 한다.
왜냐?
n = 1 일 때, n : 1과 인접해 있는 것들은 모두 score : -1로 지정이 된다.
그 후 score : -1인 것들 중 예를 들어 n = 3이라 한다면, n : 3과 인접해 있는 것들은 n : 1과 연결될 수 있는 방법이 없어 score : 1로 지정을 해도 인접하지 않는다고 본다.

고로 모든 노드를 돌면서 아직 visit 하지 않은 경우에 1로 설정을 해도 괜찮은 것이다.

그러면 인접한 노드들이 같은 그룹에 들어가게 되는 경우는 어떻게 해야 하는가?
ex) 인접리스트가 아래와 같다.
1 / 2
2 / 1 3 4
3 / 2 4
4 / 2

반복문 i = 1
color[i] = 1
visit[i] = 1

현재 now node = 1
next_node : 2
color[next_node] = -1

현재 now node = 2
next_node : 1
이미 컬러가 설정되어 있는 노드들을 확인 하려면?
if visit[next_node] and color[next_node] == color[now_node]
를 비교하자.

이미 확인한 노드를 한번 더 확인 하게 되는 경우를 방지하는 것으로
visit을 확인 한 후에
visit을 설정하자.

            if visit[now]:
                continue
            visit[now] = True

---

2021.02.15 다시 풀려고 해보다가. visit으로 체크를 한 후에 cycle을 찾는 방식으로 하려고 했는데. 이걸 어떻게 판별할지를 떠올리지 못했다. 그리고 이를 color를 이용해서 판별 하면 된다. ```python for i in graph[now]: # 이미 방문을 한 경우에 색깔이 동일한지 판별하는 조건. # 방문 했던 노드에 다시 가는 경우에, # 사이클이 발생하는 것으로 이를 통해 분류가 가능해진다. if visit[i] and color[now] == color[i]: possible = False break # 방문 자체를 하지 않은 경우에는 # 현재 이 노드가 어떤 색깔을 가지고 있는지 기록해준다. elif not visit[i]: q.append(i) color[i] = -color[now] ```

정답 코드 :

import sys
from _collections import deque

t = int(sys.stdin.readline())
for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for i in range(n + 1)]
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    visit = [False] * (n + 1)
    color = [0] * (n + 1)
    possible = True

    def BFS(start):
        global possible
        color[start] = 1
        q = deque([start])

        while q and possible:
            now = q.popleft()

            if visit[now]:
                continue
            visit[now] = True

            for i in graph[now]:
                if visit[i] and color[now] == color[i]:
                    possible = False
                    break
                elif not visit[i]:
                    q.append(i)
                    color[i] = -color[now]

    for i in range(1, n + 1):
        if not possible:
            break
        if not visit[i]:
            BFS(i)

    if possible:
        print('YES')
    else:
        print('NO')

역시 in 같은 거는 함부로 쓰는거 아니다.