นับจำนวนต้นไม้ในป่าใน C++

กำหนดจุดยอดของป่า (คอลเลกชันของต้นไม้) เป้าหมายคือการหาจำนวนต้นไม้ในป่านั้น เราจะดำเนินการนี้โดยใช้อัลกอริธึม DFS (การค้นหาครั้งแรกในเชิงลึก) บนฟอเรสต์

ตัวอย่าง

อินพุต

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

ผลลัพธ์

Count of number of trees in a forest are: 3

คำอธิบาย

จำนวนต้นไม้ที่มีอยู่ในป่าคือ −

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราใช้อัลกอริธึมการค้นหาแบบ Depth First บนกราฟแบบเรียกซ้ำ เราจะเพิ่มจำนวนขึ้นหากทุกโหนดที่เชื่อมต่อถูกทำเครื่องหมายว่าเข้าชมจากแหล่งเดียว (ซึ่งหมายความว่ามีการสร้างต้นไม้)

• หาจุดยอดจำนวนเต็มเป็นจำนวนจุดยอดบนกราฟ

• ใช้ vector vector vec[vertice] เพื่อเก็บจุดยอดเป็นจำนวนเต็ม

• ฟังก์ชั่น insert(vector vec[], int parent, int child) รับ vec[] และเพิ่มขอบระหว่างโหนดหลักและลูกในเวกเตอร์นั้น

• เพิ่ม edge โดยใช้ vec[parent].push_back(child) และ vec[child].push_back(parent)

• ฟังก์ชันที่เกิดซ้ำ (int temp, vector vec[], vector &check) ใช้ DFS บนกราฟจากจุดยอดเริ่มต้น

• Array check[temp] ใช้เพื่อตั้งค่าโหนดตามที่เยี่ยมชม/ไม่ได้เยี่ยมชมโดยใช้ true/false

• Traverse vector vec[] ใช้ for loop และถ้า check[vec[temp][i]] เป็นเท็จ callrecurred(vec[temp][i], vec, check) แบบเรียกซ้ำสำหรับโหนดที่เชื่อมต่อ

• Function Trees_Forest(vector vec[], int vertice) รับ vec[] และคืนค่าจำนวนต้นไม้ในป่าที่กำหนดเป็นรายการ adjacency ใน vec[]

• นับป่าเริ่มต้นเป็น 0

• ตรวจสอบ vector (จุดยอด, เท็จ) เพื่อทำเครื่องหมายจุดยอดของกราฟตามที่เข้าชม

• ข้ามจุดยอดทั้งหมดโดยใช้ for loop

• หาก check[i] เป็นเท็จ ให้ใช้ dfs โดยใช้ recurred(i, vec, check) และ incrementcount

• ที่ส่วนท้ายของการวนซ้ำทั้งหมดจะนับเป็นผลลัพธ์

ตัวอย่าง

#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