Tất cả đường đi từ nguồn đến đích trong C++

Mô tả bài toán

Cho đồ thị có hướng không chu trình (DAG) N đỉnh (0 đến N-1). graph[i] là danh sách đỉnh kề từ i. Tìm tất cả đường đi từ đỉnh 0 đến đỉnh N-1.

Ví dụ: [[1,2],[3],[3],[]] → [[0,1,3],[0,2,3]].

Giải thuật DFS (Backtracking)

1. Từ đỉnh 0, đệ quy DFS theo các cạnh.
2. Giữ mảng path hiện tại.
3. Khi đến đỉnh N-1, lưu path vào kết quả.
4. Quay lui: xóa đỉnh cuối khỏi path.

Vì là DAG, không cần mảng visited.

Cài đặt C++

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

void print_paths(vector<vector<int>> v) {
    cout << "[";
    for (auto& p : v) {
        cout << "[";
        for (int x : p) cout << x << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
    vector<vector<int>> res;
    void dfs(vector<vector<int>>& g, int u, int target, vector<int>& path) {
        path.push_back(u);
        if (u == target) { res.push_back(path); path.pop_back(); return; }
        for (int v : g[u]) dfs(g, v, target, path);
        path.pop_back();
    }
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path;
        dfs(graph, 0, graph.size()-1, path);
        return res;
    }
};

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

Độ phức tạp

• Thời gian: O(V + E + P * L) (P = số đường đi, L = độ dài trung bình).
• Không gian: O(V + P * L) cho kết quả và stack đệ quy.