所有可能的路径

题目链接:https://leetcode-cn.com/problems/all-paths-from-source-to-target
题目描述:

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点,空就是没有下一个结点了。
译者注:有向图是有方向的,即规定了 a→b 你就不能从 b→a 。
所有可能的路径
所有可能的路径
所有可能的路径

题解:

class Solution {
public:
    vector<vector<int>> ans;
   
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path(1, 0);
        trackingBack(0, graph.size(), graph, path);
        return ans;
    }

    void trackingBack(int cur, int n, vector<vector<int>>& graph, vector<int> &curpath)
    {
        if(cur == n - 1)
        {
            ans.push_back(curpath);
            return;
        }
        for(auto node: graph[cur])
        {
            curpath.push_back(node);
            trackingBack(node, n, graph, curpath);
            curpath.pop_back();
        }
       
    }
};

所有可能的路径

上一篇:[Backbone.js]如何处理Model里面嵌入的Collection?


下一篇:基于FPGA的二进制转BCD设计与实现(移位加3法)