Đếm số cây trong rừng trong C ++

Cho các đỉnh của một khu rừng (tập hợp các cây). Mục đích là tìm số cây trong khu rừng đó. Chúng tôi sẽ thực hiện việc này bằng cách chạy thuật toán DFS (tìm kiếm theo độ sâu đầu tiên) trên khu rừng.

Ví dụ

Đầu vào

edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} }

Đầu ra

Count of number of trees in a forest are: 3

Giải thích

Số cây hiện có trong rừng là -

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi áp dụng thuật toán tìm kiếm Độ sâu đầu tiên trên đồ thị một cách đệ quy. Chúng tôi sẽ tăng số lượng nếu mọi nút được kết nối được đánh dấu là đã truy cập từ một nguồn (nghĩa là cây được hình thành).

• Lấy một số nguyên đỉnh dưới dạng một số đỉnh trên đồ thị.

• Lấy một vectơ vectơ vec [vertice] để lưu trữ các đỉnh dưới dạng số nguyên.

• Chèn hàm (vectơ vec [], int cha, int con) lấy vec [] và thêm một cạnh giữa các nút cha và con trong vectơ đó.

• Thêm cạnh bằng vec [parent] .push_back (child) và vec [child] .push_back (parent).

• Hàm lặp lại (int temp, vector vec [], vector &check) áp dụng DFS trên đồ thị từ thời điểm đỉnh bắt đầu.

• Kiểm tra mảng [tạm thời] được sử dụng để đặt các nút là đã truy cập / không truy cập bằng cách sử dụng true / false.

• Vec-tơ truyền ngang vec [] sử dụng vòng lặp for và nếu kiểm tra [vec [temp] [i]] là sai thì hàm callrecurred (vec [temp] [i], vec, check) đệ quy cho các nút được kết nối.

• Hàm Trees_Forest (vector vec [], int vertice) nhận vec [] và trả về số lượng cây trong rừng được cung cấp dưới dạng danh sách kề trong vec [].

• Lấy số lượng rừng ban đầu là 0.

• Kiểm tra vectơ (vertice, false) để đánh dấu các đỉnh của đồ thị là đã được thăm.

• Duyệt qua tất cả các đỉnh bằng vòng lặp for.

• Nếu kiểm tra [i] là sai thì hãy áp dụng dfs bằng cách sử dụng định kỳ (i, vec, kiểm tra) và số gia tăng.

• Kết quả là ở cuối tất cả các vòng lặp.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of number of trees in a forest are: 3