궤도

문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근데 dfs를 많이 사용해봤다면 이런 생각이 들 수 있다. dfs는 가능한 정점을 찾을 때 visited를 체크하는데 그럼 2가 이미 visited 였을테니 4->2가 될리 없지 않나? 그래서 연결된 정점을 찾고 dfs를 실행할 때는 visited를 체크하지 않는다. 근데 이러면 또 이런 생각이 들 수 있다. 그럼 1->2를 가고도 2->1이 탐색 가능해지는거고 이럼 무한루프가 되는거 아닐까? 그렇기 때문에 dfs의 현재 정점과 더불어 이 정점이 어떤 정점에서 이어져온 것인지 직전 정점도 저장한다. 소스코드 #include..