글 읽기 - [python3] 1707 이분 그래프 틀린 부분을 모르겠습니다.

y305205 6년 전 0

제가 그냥 dfs로 돌아다니는 코드를 작성했는데 슬프게도 왜 틀리는지 모르겠습니다. 계속 20%에서 틀리는것 같습니다. 그리고 좀 재미있는것은

import sys
sys.setrecursionlimit(5200)

을 위에 넣으면 리밋이 커지면 런타임 에러가 뜨고, 작으면 그대로 틀렸습니다가 뜹니다. 무슨 문제일까요? 도움 부탁드립니다.

class Graph:
    def __init__(self,N,M):
        self.Ed=[[] for i in range(N+1)]
        self.N,self.M=N,M
    def isBG(self):
        clr=[-1]*(self.N+1)
        def dfs(k,c):
            clr[k]=c
            for i in self.Ed[k]:
                if clr[i]==-1:
                    return dfs(i,1-c)
                elif clr[i]==c:
                    return False
            return True
        for i in range(1,self.N+1):
            if clr[i]==-1 and not dfs(i,0):
                return False
        return True
    def append(self,L):
        self.Ed[L[0]].append(L[1])
        self.Ed[L[1]].append(L[0])
T=int(input())
for ix in range(T):
    N,M=list(map(int,input().split()))
    g=Graph(N,M)
    for i in range(M):
        g.append(list(map(int,input().split())))
    print(g.isBG() and 'YES' or 'NO')

jh05013 6년 전 1

sys.setrecursionlimit을 안 하면 틀렸습니다 말고 런타임 에러가 뜨네요. 여기서는 정점 개수만큼은 재귀가 들어갈 수 있으므로 더 큰 recursionlimit을 잡아야 하고, 그러면 틀렸습니다가 뜹니다.

y305205 6년 전 0

크게 잡으면 런타임 에러가 뜹니다 ㅠㅠ

25000,100000으로 잡아보았는데 모두 런타임 에러가 뜹니다..

jh05013 6년 전 1

이걸 제출했더니 틀렸다고 하던데요.

from sys import setrecursionlimit as SRL, stdin
input = stdin.readline
SRL(12323)

class Graph:
    def __init__(self,N,M):
        self.Ed=[[] for i in range(N+1)]
        self.N,self.M=N,M
    def isBG(self):
        clr=[-1]*(self.N+1)
        def dfs(k,c):
            clr[k]=c
            for i in self.Ed[k]:
                if clr[i]==-1:
                    return dfs(i,1-c)
                elif clr[i]==c:
                    return False
            return True
        for i in range(1,self.N+1):
            if clr[i]==-1 and not dfs(i,0):
                return False
        return True
    def append(self,L):
        self.Ed[L[0]].append(L[1])
        self.Ed[L[1]].append(L[0])
T=int(input())
for ix in range(T):
    N,M=list(map(int,input().split()))
    g=Graph(N,M)
    for i in range(M):
        g.append(list(map(int,input().split())))
    print(g.isBG() and 'YES' or 'NO')

y305205 6년 전 0

/리밋을 더 키워도 계속 틀리네요.. 방법이 없을까요? 제 코드의 틀린점을 못찾겠습니다. 도와주세요 ㅠㅠ

jh05013 6년 전 1

반례입니다. dfs가 제대로 돌아가지 않고 있는 것 같습니다.

y305205 6년 전 0

으아아 감사합니다.. Line 15에서 그냥 dfs값을 리턴하고 있었네요.. 거짓일때만 거짓을 리턴하게 해서 맞았습니다. 정말 감사합니다.

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

문제

문제

출처

ICPC

[python3] 1707 이분 그래프 틀린 부분을 모르겠습니다.

y305205 6년 전 0

jh05013 6년 전 1

y305205 6년 전 0

jh05013 6년 전 1

y305205 6년 전 0

jh05013 6년 전 1

y305205 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말