এই আর্টিকেলে আমরা গ্রাফে সিংক নোড সংখ্যা বের করার গুরুত্বপূর্ণ তথ্য বর্ণনা করব। এই সমস্যায় আমাদের কাছে একটি Directed Acyclic Graph (DAG) আছে N নোড (1 থেকে N) এবং M এজ সহ। লক্ষ্য হলো দেওয়া গ্রাফে কতটি সিংক নোড আছে সেটি বের করা। সিংক নোড হলো ওই নোড যেখান থেকে কোনো আউটগোইং এজ নেই। একটি সহজ উদাহরণ:
ইনপুট : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
আউটপুট : 2
সমাধানের সহজ পদ্ধতি
এই পদ্ধতিতে আমরা গ্রাফের এজগুলোর মাধ্যমে traverser করব, সেটে এজ যেখান থেকে যাচ্ছে সেসব ডISTINCT এলিমেন্ট রাখব, এবং তারপর সেটের আকার কোটা নোড সংখ্যা থেকে বিয়োগ করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main(){ int n = 4; // নোড সংখ্যা int m = 2; // এজ সংখ্যা vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // প্রথম থেকে دومে যাওয়া এজ set<int> s; for(int i = 0; i < m; i++){ s.insert(edges[i].first); // যেসব নোড থেকে এজ বের হচ্ছে সেগুলো ডISTINCT রেখে রাখবে } cout << n - s.size(); // উত্তর = মোট নোড - নন-সিংক নোড সংখ্যা return 0; }
আউটপুট
2
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে আমরা ভেক্টর edges traverser করি এবং পেয়ারের প্রথম এলিমেন্ট সেটে ইনসার্ট করি। সেট শুধু ডISTINCT এলিমেন্ট রাখে, তাই এখন আমরা সেটের আকার মোট নোড সংখ্যা থেকে বিয়োগ করব। উপরের প্রোগ্রামটির সময় জটিলতা O(N), যেখানে N হল গ্রাফে থাকা এজ সংখ্যা।
উপসংহার
এই আর্টিকেলে আমরা সেট ব্যবহার করে O(N) সময় জটিলতায় গ্রাফে সিংক নোড সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সমাধানের পূর্ণ পদ্ধতি শিখেছি। একই প্রোগ্রাম C, Java, Python বা অন্য ভাষায় লেখা যায়। আশা করি এই আর্টিকেলটি সহায়ক হবে।
