글 읽기 - 문제 조건 관련 오류

eric9709 3년 전 0

안녕하세요, https://www.acmicpc.net/problem/1260 질문글을 남겼었습니다.

요지는 문제에서 최소 node의 수가 1이고, 최소 edge의 수도 1개라고 되어 있는데, 이 경우에

node가 1개인 경우는 cycle이 생기는 입력이 있을 수 있는지
만약 아니라면 최소 node의 수를 2로 올리거나 edge의 최소 수를 0개로 바꿔야 할 필요가 있다

입니다.

입력부에서 node 두 개가 같은 경우(cycle이 생기는 경우)에 대해 바로 프로그램을 종료하도록 하여 실행한 결과에도 마찬가지로 정답 처리가 이루어지는 것으로 보아, node가 1개인 경우가 없거나 edge에 cycle이 없는(= 최소 edge의 수가 0개인) test case가 있는 것 같습니다.

해당 부분 확인 부탁드리며, 적절하게 조치를 취해 주시길 부탁드립니다.

첨부한 코드는 확인용으로 작성한 코드(채점 번호 20275728)입니다. 감사합니다.

import sys
import collections

def main():
    n, m, startNode = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        if a == b:
            return
        graph[a].append(b)
        graph[b].append(a)
    
    if n == 1:
        print(startNode)
        print(startNode)
        return

    bfsAns = []
    dfsAns = []

    #for i in graph:
    #    i = list(set(i))
        #i.sort()

    # BFS
    visited = [False] * (n + 1)
    stack = collections.deque([startNode])
    while stack:
        stack.append(None)
        while True:
            temp = stack.popleft()
            if temp == None:
                break
            if visited[temp]:
                continue
            visited[temp] = True
            bfsAns.append(temp)
            graph[temp].sort()
            stack += graph[temp]
    
    # DFS
    visited = [False] * (n + 1)
    stack = collections.deque([startNode])
    while stack:
        temp = stack.pop()
        if visited[temp]:
            continue
        visited[temp] = True
        dfsAns.append(temp)
        graph[temp].sort()
        stack += reversed(graph[temp])
        
    for i in dfsAns:
        print(i, end = " ")
    print("")
    for i in bfsAns:
        print(i, end = " ")
    return

if __name__ == "__main__":
    main()