একটি দিকনির্দেশিত, অ্যাসাইক্লিক গ্রাফ দেওয়া আছে যার N নোড। নোড ০ থেকে নোড N-1-এ যাওয়ার সব সম্ভাব্য পথ বের করতে হবে, যেকোনো ক্রমে ফেরত দিতে পারেন। গ্রাফ যেন: নোডগুলো ০, ১, ..., graph.length-1। graph[i] হলো সকল নোড j-র তালিকা যেন জন্য এজ (i, j) আছে।
উদাহরণ: ইনপুট [[1,2], [3], [3], []] হলে আউটপুট [[0,1,3], [0,2,3]]।
সমাধানের ধাপগুলো:
resনামের একটি ২D অ্যারে বানান।solveনামের একটি মেথড বানান যা গ্রাফ, নোড, টার্গেট আর টেম্প অ্যারে নেবে।temp-এ নোড ঢোকান।- যদি নোড == টার্গেট হয়,
temp-কেres-এ ঢোকিয়ে ফেরত যান। i = 0থেকেgraph[node].size()-1পর্যন্ত:solve(graph, graph[node][i], target, temp)কল করুন।- মূল মেথড থেকে টেম্প অ্যারে বানিয়ে
solve(graph, 0, graph.size()-1, temp)কল করুন। resফেরত দিন।
উদাহরণ (C++)
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: vector < vector <int> > res; void solve(vector < vector <int> >& graph, int node, int target, vector <int>temp){ temp.push_back(node); if(node == target){ res.push_back(temp); return; } for(int i = 0; i < graph[node].size(); i++){ solve(graph, graph[node][i], target, temp); } } vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { vector <int> temp; solve(graph, 0, graph.size() - 1, temp); return res; } }; main(){ vector<vector<int>> v = {{1,2},{3},{3},{}}; Solution ob; print_vector(ob.allPathsSourceTarget(v)); }ইনপুট
[[1,2],[3],[3],[]]
আউটপুট
[[0, 1, 3, ],[0, 2, 3, ],]
