글 읽기 - 1707 파이썬 질문

jungry 3년 전 0

그래프 안의 값들을 확인하면서 만약 다음 그래프의 visit 값과 현재의 visit 값이 같으면 NO 가 나오게 만들었습니다 (제대로 맞는지는 잘 모르겠지만요 ㅜㅜ) 정답률은 50프로정도에서 틀렸다고 나옵니다 어느부분이 틀렸는지 반례를 알려주실수 있으신가용 ?_?

#1707 이분 그래프

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(now,visit,color): #color = 어떤 이분탐색쪽인지 (이전꺼랑 서로 달라야함)
    global result
    for i in arr[now]:
        visit[now] = color
        if visit[i] == False:
            dfs(i,visit,(color)*-1)
        if visit[i] != False:
            if visit[i] == visit[now]:
                result = False
    return

tc = int(input())
for _ in range(tc):
    n,m = map(int,input().split()) #정점 , 간선
    arr = [[] for _ in range(n+1)] #간선 정보
    for _ in range(m):
        a,b = map(int,input().split())
        arr[a].append(b)
        arr[b].append(a)
    visit = [False] * (n+1) #방문 정보
    result = True
    dfs(1,visit,1)
    if result:
        print('YES')
    elif not result:
        print('NO')

doju 3년 전 1

주어진 그래프가 연결된 그래프가 아닐 수 있습니다.

jungry 3년 전 0

아 당연히 연결그래프 일거라고 생각했네요 감사합니다 !!

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

문제

문제

출처

ICPC

1707 파이썬 질문

jungry 3년 전 0

doju 3년 전 1

jungry 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말