글 읽기 - 반례 부탁드립니다

plse 1년 전 0

예제는 맞았는데 틀렸다고 나오네요

반례 찾아주시면 감사하겠습니다

#DFS
import sys
from collections import deque
sys.setrecursionlimit(10000000)
input=sys.stdin.readline
def dfs(graph,start_node):
    global visited
    queue=deque()
    queue.append(start_node)
    while queue:
        node=queue.pop()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return
        
v,e=map(int,input().split())
visited=[]
cnt=0
graph=[[] for x in range(v+1)]
for i in range(e):
    a,b=map(int,input().split())
    graph[a].append(b)
for x in range(1,v+1):
    if x in visited:
        continue
    else:
        dfs(graph,x)
        cnt+=1
print(cnt)

rlackstjq987 1년 전 0

11724 번 문제 2년 전 shg9411 님이 올려주신 반례입니다.

input )

3 2
3 1
2 1

output)

문제에서 간선은 방향이 없는 간선입니다.

반례로 알 수 있듯이, 1번 노드와 3번 노드 사이에는 간선이 있음에도, line 23 에서 x 가 1일때 dfs 함수 내 line13 의 graph[1] 를 방문하면 1번 노드와 연결된 간선이 없다는 뜻인 빈 배열을 삽입하게 됩니다.

간선 정보를 담는 graph 배열에서 a to b 뿐만 아니라 b to a 또한 고려하도록 해보세요!

추가로, plse 님이 사용하신 deque 를 사용하는 탐색법은 dfs ( Depth First Search ) 가 아닌 bfs (Breadth First Search) 입니다. 저도 헷갈리기도 했었고, 알고리즘의 이름이 중요한 것은 아니지만 참고하시라고 말씀드립니다.

mizuharaeki 1년 전 0

무방향 그래프입니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다

plse 1년 전 0

rlackstjq987 1년 전 0

mizuharaeki 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말