প্রদত্ত একটি বনের শীর্ষবিন্দু (গাছের সংগ্রহ)। লক্ষ্য হল সেই বনে গাছের সংখ্যা বের করা। আমরা বনে একটি DFS (গভীরতার প্রথম অনুসন্ধান) অ্যালগরিদম চালিয়ে এটি করব৷
উদাহরণস্বরূপ
ইনপুট
edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} } আউটপুট
Count of number of trees in a forest are: 3
ব্যাখ্যা
বনে থাকা গাছের সংখ্যা হল −
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা গ্রাফে পুনরাবৃত্তভাবে ডেপথ ফার্স্ট সার্চ অ্যালগরিদম প্রয়োগ করি। প্রতিটি সংযুক্ত নোডকে একটি উৎস থেকে পরিদর্শন করা হলে আমরা গণনা বৃদ্ধি করব (যার মানে একটি গাছ তৈরি হয়)।
-
একটি গ্রাফে অনেকগুলি শীর্ষবিন্দু হিসাবে একটি পূর্ণসংখ্যার শীর্ষবিন্দু নিন৷
৷ -
পূর্ণসংখ্যা হিসাবে শীর্ষবিন্দু সংরক্ষণের জন্য একটি ভেক্টর ভেক্টর
vec[vertice] নিন। -
ফাংশন সন্নিবেশ (ভেক্টর
vec[], int পিতামাতা, int চাইল্ড) vec[] নেয় এবং সেই ভেক্টরে পিতামাতা এবং শিশুর মধ্যে একটি প্রান্ত যোগ করে। -
vec[parent].push_back(child) এবং vec[child].push_back(parent) ব্যবহার করে প্রান্ত যোগ করুন।
-
পুনরাবৃত্ত ফাংশন (int temp, vector
vec[], vector &check) গ্রাফে শুরু ভার্টেক্স টেম্প থেকে DFS প্রয়োগ করে। -
অ্যারে চেক[টেম্প] সত্য/মিথ্যা ব্যবহার করে নোডকে ভিজিট/অভিজিটেড হিসেবে সেট করতে ব্যবহৃত হয়।
-
ট্রাভার্স ভেক্টর vec[] লুপের জন্য ব্যবহার করে এবং চেক[vec[temp][i]] মিথ্যা হলে সংযুক্ত নোডের জন্য পুনরাবৃত্তভাবে (vec[temp][i], vec, check) কল করুন।
-
ফাংশন Trees_Forest(vector
vec[], int vertice) vec[] নেয় এবং vec[]-এ সংলগ্ন তালিকা হিসাবে দেওয়া বনের গাছের সংখ্যা ফেরত দেয়। -
বনের প্রাথমিক গণনা 0 হিসাবে নিন।
-
গ্রাফের শীর্ষবিন্দুগুলিকে পরিদর্শন করা হিসাবে চিহ্নিত করতে ভেক্টর
চেক (উল্লম্ব, মিথ্যা) নিন। -
লুপ ব্যবহার করে সমস্ত শীর্ষবিন্দু অতিক্রম করুন৷
৷ -
চেক[i] মিথ্যা হলে পুনরাবৃত্ত (i, vec, check) এবং incrementcount ব্যবহার করে dfs প্রয়োগ করুন।
-
সমস্ত লুপের শেষে ফলাফল হিসাবে গণনা ফিরে আসে।
উদাহরণ
#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
