글 읽기 - 게시판에 나온 반례들 다점검했는데 50%즈음에 틀렸다고 나오네요

jkit 3년 전 0

음... Q&A보면서 몇가지 수정해서 런타임에러같은거는 고쳤는데

50%에서 막히네요.. 혹시 어떤 것이 문제일까요?

import sys
from collections import deque


# 그래프 만들기
def makeGrape(grape):
    t_grape = {}
    for i in grape:
        if i[0] not in t_grape:
            t_grape[i[0]] = {i[1]}
        else:
            t_grape[i[0]].add(i[1])
        if i[1] not in t_grape:
            t_grape[i[1]] = {i[0]}
        else:
            t_grape[i[1]].add(i[0])
    return t_grape


def bfs(V, E, grape):
    if V == 1 and E == 1:
        return print('YES')
    q = deque()
    t_grape = makeGrape(grape)
    q.append(grape[0][0])
    chk = [0 for _ in range(V+1)]
    chk[grape[0][0]] = 1

    # print(t_grape)
    while q:       
        a = q.popleft()
        b = t_grape[a]
        for i in b:
            # print(chk)
            if chk[i] == 0:
                chk[i] = chk[a] + 1
                q.append(i)
                continue
            if (chk[i] % 2) == (chk[a] % 2):
                return print("NO")
    return print("YES")


if __name__ == "__main__":
    T = int(sys.stdin.readline().strip())
    for _ in range(T):
        V, E = map(int, sys.stdin.readline().split())
        grape = []
        for _ in range(E):
            grape.append(list(map(int, sys.stdin.readline().split())))
        bfs(V, E, grape)

kimhyeun 3년 전 6

5 4

1 2

3 4

4 5

3 5

이거 한번 해보세요. NO 나와야 됩니다

jkit 3년 전 0

kimhyeun 님 감사합니다 여러각도에서 시작하는 코드를 추가하니 해결되었네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

게시판에 나온 반례들 다점검했는데 50%즈음에 틀렸다고 나오네요

jkit 3년 전 0

kimhyeun 3년 전 6

jkit 3년 전 0

kimhyeun 님 감사합니다 여러각도에서 시작하는 코드를 추가하니 해결되었네요!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말