글 읽기 - 1707번 문제 이분그래프 반례 궁금합니다.

dlsghl1215 2년 전 0

굳이 그래프 안쓰고 직관적으로 했는데 여기 게시판에 있는 모든 반례해봐도 다 맞는데 뭐가 문제인가요?

t = int(input())

for tc in range(t):
    v, e = map(int, input().split())

    graph = [0] * 20001

    result = True
    for i in range(e):
        x, y = map(int, input().split())

        if graph[x] == 0 and graph[y] == 0:
            graph[x] = -1
            graph[y] = 1
            continue

        elif (graph[x] == -1 or graph[x] == 1) and graph[y] == 0:
            graph[y] = -graph[x]
            continue

        elif (graph[y] == -1 or graph[y] == 1) and graph[x] == 0:
            graph[x] = -graph[y]
            continue

        else:
            if graph[x] == graph[y]:
                result = False
                break

    if result:
        print("YES")
    else:
        print("NO")

Green55 2년 전 0

graph[x] == 0 and graph[y] == 0 일 때 x에 1을, y에 -1을 배정해야 답이 되는 경우가 있을 수 있습니다.

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

문제

문제

출처

ICPC

1707번 문제 이분그래프 반례 궁금합니다.

dlsghl1215 2년 전 0

Green55 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말