ทุกเส้นทางจากต้นทางไปปลายทางใน C++

ให้กราฟมีทิศทาง (directed) และไม่มีวัฏจักร (acyclic) มีโหนด 0, 1, ..., N-1 โดย graph[i] = รายการโหนด j ที่มีเส้นจาก i → j ต้องการหา ทุกเส้นทาง จากโหนด 0 ไปโหนด N-1

ตัวอย่าง: graph = [[1,2],[3],[3],[]] → [[0,1,3],[0,2,3]]

ขั้นตอนการแก้ปัญหา (DFS + Backtracking)

1. สร้างอาร์เรย์ 2D res เก็บผลลัพธ์
2. ฟังก์ชัน solve(graph, node, target, temp):
   • ใส่ node เข้า temp
   • ถ้า node == target ใส่ temp เข้า res และคืน
   • วนลูปเพื่อนบ้านของ node เรียก solve ต่อ
3. เริ่มจาก solve(graph, 0, N-1, {})
4. คืน res

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (auto& row : v) {
        cout << "[";
        for (int x : row) cout << x << ", ";
        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 nxt : graph[node]) solve(graph, nxt, target, temp);
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> temp;
        solve(graph, 0, graph.size()-1, temp);
        return res;
    }
};

int main() {
    vector<vector<int>> v = {{1,2},{3},{3},{}};
    Solution ob;
    print_vector(ob.allPathsSourceTarget(v));
}

Input

[[1,2],[3],[3],[]]

Output

[[0, 1, 3, ],[0, 2, 3, ],]