ফরেস্টে ট্রির সংখ্যা গণনা 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

ব্যাখ্যা

ফরেস্টে থাকা ট্রিগুলোর সংখ্যা নিচে দেখানো হলো:

প্রোগ্রামে ব্যবহৃত পদ্ধতি:

এই পদ্ধতিতে আমরা গ্রাফে ডেপথ ফার্স্ট সার্চ অ্যালগরিদম রিকারসিভলি অ্যাপ্লাই করি। যদি একটি সোর্স থেকে সব কানেক্টেড নোড ভিজিটেড মার্ক হয় (যা মানে একটি ট্রি তৈরি হয়েছে) তবে কাউন্ট বাড়ানো হয়।

• ইন্টিজার vertice গ্রাফের ভার্টেক্স সংখ্যা হিসেবে।
• vector<int> vec[vertice] ভার্টেক্স স্টোর করার জন্য।
• insert(vector<int> vec[], int parent, int child) ফাংশন ভেক্টরে পেরেন্ট এবং চাইল্ডের মধ্যে এজ যোগ করে।
• vec[parent].push_back(child) এবং vec[child].push_back(parent) দিয়ে এজ যোগ।
• recurred(int temp, vector<int> vec[], vector<bool> &check) ফাংশন স্টার্টিং ভার্টেক্স থেকে গ্রাফে DFS অ্যাপ্লাই করে।
• check[temp] অ্যারে নোড ভিজিটেড/অনভিজিটেড মার্ক করতে true/false দিয়ে।
• ভেক্টর vec[] ট্রভারস করে যদি check[vec[temp][i]] false হয় তবে রিকারসিভ কল recurred(vec[temp][i], vec, check)।
• Trees_Forest(vector<int> vec[], int vertice) ফাংশন vec[] এবং vertice নিয়ে ফরেস্টের ট্রি কাউন্ট রিটার্ন করে।
• ইনিশিয়াল কাউন্ট ০। vector<bool> check(vertice, false) ভিজিটেড মার্ক করার জন্য।
• সব ভার্টেক্স ট্রভারস করে যদি check[i] false হয় তবে recurred(i, vec, check) কল করে count++।
• সব লুপ শেষে 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