1260번 - DFS와 BFS
안녕하세요, 1260번 "DFS와 BFS"를 풀고 궁금한 점이 있어 글을 작성합니다.
문제에는 "어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다"라고 되어 있습니다.
따라서 정점 u와 v 사이에 M개보다 작거나 같은 수의 간선이 존재할 수 있다고 생각했습니다.
처음에는 제출 번호: 97030976 코드를 제출했는데, 답이 맞았다고 하였습니다.
그러나 testcase.ac에 같은 코드를 돌려본 결과 반례가 발생하였습니다.
대표적인 반례로는 아래와 같습니다.
위의 코드의 문제가 무엇인가 하고 보았더니
저는 그래프를 adjacency list로 표현하였는데, 인접한 정점을 중복을 허용하여 (M+1)개가 아닌 N개를 넣었더니 seg fault가 뜬 것이었습니다.
그래서 제출 번호: 97031576 코드로 바꾸었고, 여전히 정답이었습니다.
혹시 테스트 케이스가 추가되어야 할까요?
감사합니다.
댓글을 작성하려면 로그인해야 합니다.
hemisphere1357 1년 전
안녕하세요, 1260번 "DFS와 BFS"를 풀고 궁금한 점이 있어 글을 작성합니다.
문제에는 "어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다"라고 되어 있습니다.
따라서 정점 u와 v 사이에 M개보다 작거나 같은 수의 간선이 존재할 수 있다고 생각했습니다.
처음에는 제출 번호: 97030976 코드를 제출했는데, 답이 맞았다고 하였습니다.
그러나 testcase.ac에 같은 코드를 돌려본 결과 반례가 발생하였습니다.
대표적인 반례로는 아래와 같습니다.
위의 코드의 문제가 무엇인가 하고 보았더니
저는 그래프를 adjacency list로 표현하였는데, 인접한 정점을 중복을 허용하여 (M+1)개가 아닌 N개를 넣었더니 seg fault가 뜬 것이었습니다.
그래서 제출 번호: 97031576 코드로 바꾸었고, 여전히 정답이었습니다.
혹시 테스트 케이스가 추가되어야 할까요?
감사합니다.