주어진 그래프가 단방향 그래프이고 위의 방법과 같이 코드를 작성했을 경우
dfs가 동작할 때 O(N)보다 많은 시간이 걸릴 수도 있습니다.
6개의 노드에 아래와 같은 단방향 간선으로 그래프가 연결되어 있을 때,
1 -> 2
2 -> 3
3 -> 4
1 -> 5
1 -> 6
5 -> 2
6 -> 2
dfs가 들리는 정점 번호는
1 -> 2 -> 3 -> 4 이후 2, 3, 4에서 visit을 다시 false로 만들어주어
5 -> 2 -> 3 -> 4
6 -> 2 -> 3 -> 4 와 같이 2, 3, 4번 노드를 다시 방문할 것이라 생각이 드네요.
convert7342 3년 전
1 ~ 67번줄 코드는 시간초과 코드이고
71번줄 부터의 코드는 AC가 뜬 코드입니다.
인접 리스트를 이용해 a, b 를 입력받아 [b] 인덱스에 a를 푸시해주는 방식으로
모든 노드에 대하여 dfs를 이용해 탐색했습니다.
두 코드의 차이는 dfs마다 visit를 true로 이용 한 뒤 false로 그때마다 바꿔주는 것과 memset 을 이용해 visit를 초기화 하는 차이가 있습니다.
memset을 이용했을 때는 시간초과가 발생하지 않았는데
윗부분의 코드에서 제가 발견하지 못한 오류가 있을지 여쭤봅니다.