4803번 - 트리
그래프를 양방향 매핑해 인접 리스트로 저장합니다.
각 노드마다 BFS 또는 DFS를 사용해 그래프를 순회하면서, 순회하는 중인 트리의 간선과 정점 개수를 셉니다. (함수 isTree에서 변수 numOfEdge, numOfVertex)
isTree
numOfEdge
numOfVertex
양방향으로 매핑했기에, (numOfEdge / 2) == (numOfVertex - 1)이면 트리입니다.
(numOfEdge / 2) == (numOfVertex - 1)
모든 노드에 대해 이를 반복하면 주어진 입력에서의 트리 수를 셀 수 있습니다.
이를 구현한 C++ 코드는 여기에서 보실 수 있습니다.
혹시 더 간단한 풀이가 있다면 말씀해 주세요. 제목이나 본문을 수정하겠습니다...
이 풀이는 zenith82114님의 도움을 받았습니다.
처음 풀이: bfs만을 함수로 따로 빼서, 정점 배열을 반환하게 해 solve 함수에서 edge의 수를 셈.
본문과 코드를 수정했습니다! 조언 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
molla12 2년 전
그래프를 양방향 매핑해 인접 리스트로 저장합니다.
각 노드마다 BFS 또는 DFS를 사용해 그래프를 순회하면서, 순회하는 중인 트리의 간선과 정점 개수를 셉니다. (함수
isTree에서 변수numOfEdge,numOfVertex)양방향으로 매핑했기에,
(numOfEdge / 2) == (numOfVertex - 1)이면 트리입니다.모든 노드에 대해 이를 반복하면 주어진 입력에서의 트리 수를 셀 수 있습니다.
이를 구현한 C++ 코드는 여기에서 보실 수 있습니다.
혹시 더 간단한 풀이가 있다면 말씀해 주세요. 제목이나 본문을 수정하겠습니다...
이 풀이는 zenith82114님의 도움을 받았습니다.
처음 풀이: bfs만을 함수로 따로 빼서, 정점 배열을 반환하게 해 solve 함수에서 edge의 수를 셈.