주어진 숲의 정점(나무 모음). 목표는 그 숲에 있는 나무의 수를 찾는 것입니다. 포리스트에서 DFS(깊이 우선 검색) 알고리즘을 실행하여 이를 수행합니다.
예를 들어
입력
edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} } 출력
Count of number of trees in a forest are: 3
설명
숲에 존재하는 나무의 수는 -
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서는 그래프에 깊이 우선 탐색 알고리즘을 재귀적으로 적용합니다. 연결된 모든 노드가 하나의 소스(트리가 형성됨을 의미)에서 방문한 것으로 표시되면 카운트를 증가시킵니다.
-
정수 정점을 그래프의 정점 수로 가져옵니다.
-
정점을 정수로 저장하기 위한 벡터 vector
vec[vertice]를 사용합니다. -
함수 insert(vector
vec[], int parent, int child)는 vec[]를 가져와서 해당 벡터의 부모 노드와 자식 노드 사이에 가장자리를 추가합니다. -
vec[parent].push_back(child) 및 vec[child].push_back(parent)를 사용하여 가장자리를 추가합니다.
-
함수 recurred(int temp, vector
vec[], vector &check)는 시작 정점 온도에서 그래프에 DFS를 적용합니다. -
Array check[temp]는 true/false를 사용하여 노드를 방문/미방문으로 설정하는 데 사용됩니다.
-
for 루프를 사용하여 벡터 vec[]를 트래버스하고 check[vec[temp][i]]가 거짓이면 연결된 노드에 대해 재귀적으로 callrecurred(vec[temp][i], vec, check)를 호출합니다.
-
함수 Trees_Forest(vector
vec[], int vertice)는 vec[]를 받아서 vec[]에 인접 목록으로 제공된 숲의 나무 수를 반환합니다. -
숲의 초기 수를 0으로 간주합니다.
-
vector
check(vertice, false)를 사용하여 그래프의 정점을 방문한 것으로 표시합니다. -
for 루프를 사용하여 모든 정점을 순회합니다.
-
check[i]가 거짓이면 recurred(i, vec, check) 및 incrementcount를 사용하여 dfs를 적용하십시오.
-
모든 루프가 끝나면 count를 결과로 반환합니다.
예시
#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
vec[parent].push_back(child);
vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
check[temp] = true;
int size = vec[temp].size();
for(int i = 0; i < size; i++){
if (check[vec[temp][i]] == false){
recurred(vec[temp][i], vec, check);
}
}
}
int Trees_Forest(vector<int> vec[], int vertice){
int count = 0;
vector<bool> check(vertice, false);
for(int i = 0; i < vertice; i++){
if(check[i] == false){
recurred(i, vec, check);
count++;
}
}
return count;
}
int main(){
int vertice = 9;
vector<int> vec[vertice];
insert(vec, 1, 3);
insert(vec, 2, 8);
insert(vec, 2, 6);
insert(vec, 3, 5);
insert(vec, 3, 7);
insert(vec, 4, 8);
cout<<"Count of number of trees in a forest are: "<<Trees_Forest(vec, vertice);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of number of trees in a forest are: 3