একটি অনির্দেশিত গ্রাফ এবং ভার্টেক্সের একটি সেট দেওয়া আছে। সেটের প্রতিটি ভার্টেক্স থেকে পৌঁছানো যাওয়া সব নোড (reachable nodes) খুঁজে বের করুন।
ইনপুট গ্রাফ (চিত্র): ১-২-৩ এবং ৪-৫ দুটি কানেক্টেড কম্পোনেন্ট। আউটপুট: [1,2,3] এবং [4,5]
সমাধানের ধাপসমূহ
- visited অ্যারে এবং ম্যাপ m রাখুন।
- সেটের প্রতিটি নোড u-এর জন্য: যদি ভিজিটেড না হয়, কম্পোনেন্ট কাউন্ট বাড়ান, BFS করুন u থেকে পৌঁছানো যাওয়া নোডগুলো m-এ সংরক্ষণ করুন।
- প্রতিটি u-এর জন্য m[visited[u]] প্রিন্ট করুন।
উদাহরণ (C++ কোড)
#include <bits/stdc++.h>
using namespace std;
class Graph {
public:
int nodes; list* adj_list;
Graph(int n) { nodes=n; adj_list=new list[n+1]; }
void insert_edge(int u,int v) { adj_list[u].push_back(v); adj_list[v].push_back(u); }
vector BFS(int comp_sum, int src, int visited[]) {
queue q; q.push(src); visited[src]=comp_sum;
vector reachable;
while(!q.empty()) {
int u=q.front(); q.pop(); reachable.push_back(u);
for(int v:adj_list[u]) if(!visited[v]) { visited[v]=comp_sum; q.push(v); }
}
return reachable;
}
};
void displayReachableNodes(int n, unordered_map>& m) {
for(int x:m[n]) cout<> m; int comp_sum=0;
for(int i=0;i
ইনপুট
Edges: 1-2, 2-3, 4-5; Query nodes: 2,4,1
আউটপুট
Reachable Nodes from 2 are 2 1 3
Reachable Nodes from 4 are 4 5
Reachable Nodes from 1 are 2 1 3
