chhc0505   2년 전

Q1. DFS를 이용해 무방향그래프 내 모든 싸이클을 탐지, 제거해서 트리로 만들 수 있나요?

Q2. 그래프에서 싸이클을 제거해서 트리를 만드는 좋은 문제 있을까요??

pill27211   2년 전

이중 연결 요소(Biconnected Component)에 대해 공부해 보시면 될 것 같습니다. 단절점과 단절선, SCC 등에 대한 배경 지식이 있다면 보다 수월하게 이해할 수 있습니다.

대표적으로 이 문제의 경우, 질문하신 Q2의 작업을 통해 이 문제로 환원하여 풀 수 있습니다.

chhc0505   2년 전

답글 정말 감사합니다 !!

열심히 공부해보겠습니다 ㅎㅎ

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