백준 1707: 이분그래프 (Python)

 

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

1707번: 이분 그래프

 

날 아주아주아주아주 화나게 한 문제다

맞는 거 같은데 자꾸 틀려서 열심히 반례 찾고 다녔다

 

예시 입력1

2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2

예시 출력1

YES NO

 

예시 입력2

11  3 1  2 3  3 2  1 3  2 3  4 4  1 2  2 3  3 4  4 2  3 2  2 1  3 2  4 4  2 1  3 2  4 3  4 1  5 2  1 5  1 2  5 2  1 2  2 5  4 3  1 2  4 3  2 3  4 4  2 3  1 4  3 4  1 2  3 3  1 2  2 3  3 1  2 1  1 2

예시 출력2

YES  YES  NO  YES  YES  YES  YES  YES  YES  NO  YES

 

예시 입력3

1  4 3  1 4  2 3  3 4

예시 출력3

YES

 

예시 입력4

1 5 4 1 2 3 4 3 5 4 5

예시 출력4

NO

 

 

from collections import deque

k = int(input())
res = [[] for _ in range(k)]

def bfs(x):
    queue = deque()
    queue.append(x)

    flag = 0
    visited[x] = [1, flag]

    while queue:
        q = queue.popleft()
        flag = 1 - visited[q][1]

        for i in graph[q]:
            if visited[i][0] == 0:
                queue.append(i)
                visited[i] = [1, flag]
                for j in graph[i]:
                    if visited[i][1] == visited[j][1]:
                        return False

    return True

for i in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [[0, 20000] for _ in range(v + 1)]
    res[i] = "YES"
    for j in range(e):
        data = input().split()
        graph[int(data[0])].append(int(data[1]))
        graph[int(data[1])].append(int(data[0]))
    for l in range(1, v+1):
        if visited[l][0] == 0:
            if not bfs(l):
                res[i] = "NO"
                break

for i in range(k):
    print(res[i])

 

 

일단 내가 간과했던 점은 그래프 전체가 연결되어 있지 않은 것도 있기 때문에

bfs를 돌릴 때 떨어져 있는 그래프들을 모두 돌려줘야 한다

진짜 너무 힘들었다,,,,,,,, 된 거 같은데?! 하면 자꾸 틀린 반례가 나옴ㅋㅋㅋㅋㅋㅋ

코드가 너무 비효율적인 거 같아서 좀 고쳐서 파이썬3으로 다시 돌려보려고 하는데

일단 지금은 기빨려서 더이상 쳐다보고 싶지 않으니 다음에 해야겠다

 

맨 마지막 제출은 실수로 두번 눌러서,,,,