molla12   2년 전

그래프를 양방향 매핑해 인접 리스트로 저장합니다.

각 노드마다 BFS 또는 DFS를 사용해 그래프를 순회하면서, 순회하는 중인 트리의 간선과 정점 개수를 셉니다. (함수 isTree에서 변수 numOfEdge, numOfVertex)

양방향으로 매핑했기에, (numOfEdge / 2) == (numOfVertex - 1)이면 트리입니다.

모든 노드에 대해 이를 반복하면 주어진 입력에서의 트리 수를 셀 수 있습니다.

이를 구현한 C++ 코드는 여기에서 보실 수 있습니다.

혹시 더 간단한 풀이가 있다면 말씀해 주세요. 제목이나 본문을 수정하겠습니다...

이 풀이는 zenith82114님의 도움을 받았습니다.

처음 풀이: bfs만을 함수로 따로 빼서, 정점 배열을 반환하게 해 solve 함수에서 edge의 수를 셈.

zenith82114   2년 전

정점 목록을 만들어서 또 순회하지 말고 BFS 돌릴 때 세버리는 것도 가능할 것 같습니다.

molla12   2년 전

본문과 코드를 수정했습니다! 조언 감사합니다.

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