এই নিবন্ধে, আমরা একটি গ্রাফে সিঙ্ক নোডের সংখ্যা সমাধানের গুরুত্বপূর্ণ তথ্য বর্ণনা করব। এই সমস্যায় আমাদের কাছে N নোড (1 থেকে N) এবং M প্রান্ত সহ একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ রয়েছে। লক্ষ্য হল প্রদত্ত গ্রাফে কতগুলি সিঙ্ক নোড রয়েছে তা খুঁজে বের করা। একটি সিঙ্ক নোড এমন একটি নোড যা কোনো বহির্গামী প্রান্ত তৈরি করে না। তাই এখানে একটি সহজ উদাহরণ -
Input : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
Output : 2 সমাধান খোঁজার সহজ পদ্ধতি
এই পদ্ধতিতে, আমরা গ্রাফের প্রান্তের মধ্য দিয়ে যাব, সেটের স্বতন্ত্র উপাদানগুলিকে ধাক্কা দেব যে প্রান্তগুলি থেকে যাচ্ছে এবং তারপরে উপস্থিত নোডগুলির মোট সংখ্যা সহ সেটের আকার বিয়োগ করব৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 4; // number of nodes.
int m = 2; // number of edges.
vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
set<int> s;
for(int i = 0; i < m; i++){
s.insert(edges[i].first); // will keep value of
// distinct node from which edges are going out.
}
cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
return 0;
} আউটপুট
2
উপরের কোডের ব্যাখ্যা
এই কোডে, আমরা ভেক্টর প্রান্তের মধ্য দিয়ে অতিক্রম করব এবং একটি সেটে জোড়ার প্রথম উপাদান সন্নিবেশ করব। এটি শুধুমাত্র স্বতন্ত্র উপাদান রাখে, তাই এখন আমরা মোট নোডের সংখ্যা থেকে সেটের নির্দিষ্ট আকার বিয়োগ করব। উপরে দেখানো প্রোগ্রামটিতে O(N) এর সময় জটিলতা রয়েছে যেখানে N মানে একটি গ্রাফে উপস্থিত প্রান্তের সংখ্যা।
উপসংহার
এই নিবন্ধে, আমরা একটি সেটের সাহায্যে একটি গ্রাফ O(N) সময় জটিলতায় উপস্থিত সিঙ্ক নোডের সংখ্যা খুঁজে বের করার সমস্যার সমাধান করেছি। এছাড়াও আমরা এই সমস্যার জন্য C++ প্রোগ্রাম শিখেছি এবং সম্পূর্ণ পদ্ধতির মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
