글 읽기 - 틀렸습니다. 라고 나오는데 뭔지 정말 모르겠습니다.

nau13 1년 전 0

아래와 같이 코드를 짰는데 (근본이 없어서 코드가 더럽습니다.)

질문검색 끝페이지까지 전부 반례 넣어봤는데 정상 작동하는 것 같습니다.

제발 도움 부탁드립니다 ㅠㅠ

import sys
sys.setrecursionlimit(200000)


def dfs(start):
    visited[start] = 1
    global pre_color
    if pre_color == 0:  # 처음 도는거
        b_graph[start] = 1
        pre_color = 1
    elif pre_color == 1:
        b_graph[start] = -1
        pre_color = -1
    elif pre_color == -1:
        b_graph[start] = 1
        pre_color = 1
    # print(b_graph, pre_color)
    for i in adj_list[start]:
        if b_graph[i] == b_graph[start]:
            isitb_graph.append(-1)
        if visited[i] == 0:
            dfs(i)


testcase_N = int(sys.stdin.readline())
for _ in range(testcase_N):
    isitb_graph = []
    N, LineNum = map(int, sys.stdin.readline().split())
    adj_list = [[] for _ in range(N+1)]
    for _ in range(LineNum):
        n, m = map(int, sys.stdin.readline().split())
        adj_list[n].append(m)
        adj_list[m].append(n)
    for i in range(1,N+1):
        adj_list[i].sort()

    visited = [0 for _ in range(N+1)]
    b_graph = [0 for _ in range(N+1)]
    pre_color = 0

    dfs(1)
    for i in range(1,N+1):
        if visited[i] == 0:
            dfs(i)

    # print("b_graph", b_graph)
    # print("visited", visited)
    # print(isitb_graph)

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

Green55 1년 전 2

pre_color를 global로 두시면, dfs(x)에서 dfs(y)를 호출했다고 해도, dfs(y)에서의 pre_color는 x의 color가 아닐 수 있습니다. dfs의 호출 순서를 생각해보세요.

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

문제

문제

출처

ICPC

틀렸습니다. 라고 나오는데 뭔지 정말 모르겠습니다.

nau13 1년 전 0

Green55 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말