bj1707 이분 그래프

첨에 왜 틀렸지 했음.. 난 완전 잘 했는데 계속 틀렸다길래..
도저히 이거 말고 모르겠다고 생각이 되어서 결국 답을 봤음.
아... 연결된 노드 구조면 상관없는데 분리된 노드가 존재하는 경우도 살펴봐주어야 했음... 테스트 케이스만 보고 start를 1로 준 내 잘못.ㅋㅋㅋㅋ

아래 코드는 잘못된 코드.

import sys
from collections import deque
sys.stdin = open('test.txt', 'r')


def dfs(graph, start, visit):
    # stack 구조 사용
    stack = [start]
    # 시작은 1번 group!
    visit[start] = 1
    while stack:
        v = stack.pop()
        for i in graph[v]:
            if not visit[i]:
                stack.append(i)
                # 새로 발견된 node들은 -1번 group!
                visit[i] = -1 * visit[v]
            # 발견된 group중에서 group이 같은지 check
            elif visit[i] == visit[v]:
                print(visit)
                return print("NO")
    print(visit)
    print("YES")


n = int(input())

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    card = [[] for _ in range(a+1)]
    visit = [False] * (a+1)
    for _ in range(b):
        x, y = map(int, sys.stdin.readline().split())
        card[x].append(y)
        card[y].append(x)
    dfs(card, 1, visit)

수정된 code는 다음과 같다. 근데 이미 정답을 봐버리고 작성한 상태라 로직이 똑같음.. flag라는 변수를 사용해서 깃발이 내려간 상태라면 NO를 출력하도록 하고 함수가 정상적으로 종료되어 깃발이 올라간 상태라면 YES를 출력하도록 했다!

import sys
from collections import deque
sys.stdin = open('test.txt', 'r')


def bfs(graph, start, visit):
    # queue 구조 사용
    queue = deque([])
    queue.append(start)
    # 시작은 1번 group!
    visit[start] = 1
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visit[i]:
                queue.append(i)
                # 새로 발견된 node들은 -1번 group!
                visit[i] = -1 * visit[v]
            # 발견된 group중에서 group이 같은지 check
            elif visit[i] == visit[v]:
                return -1
    return 1


n = int(input())

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    card = [[] for _ in range(a+1)]
    visit = [False] * (a+1)
    flag = 0
    for _ in range(b):
        x, y = map(int, sys.stdin.readline().split())
        card[x].append(y)
        card[y].append(x)
    for i in range(1, a+1):
        if not visit[i]:
            flag = bfs(card, i, visit)
            if flag == -1:
                print("NO")
                break;
    if flag == 1:
        print("YES")