leetcode 797.所有可能的路径

思路：dfs。

其实很简单，我们只需要和昨天做的题一样，直接遍历所给数组中的元素，因为这里的数组意义已经很清楚了，就是当前位置的结点和哪一个顶点有联系。

注意：在存储路径的时候，我们需要按顺序存储，而不能在状态标志完之后再统计路径，这样的话顺序是不对的。

class Solution {
public:
vector<int>ans;
void init(){
    ans.push_back(0);
}
void dfs(int u,vector<vector<int>>&s,vector<bool>&st,vector<vector<int>>&res){
    if(u>s.size())return;
    if(u==s.size()-1){
        res.push_back(ans);
        return;
    }
    for(int i=0;i<s[u].size();i++){
        int num=s[u][i];
        if(!st[num]){
            st[num]=1;
            ans.push_back(num);
            dfs(num,s,st,res);
            if(ans.size()>=2)
            ans.pop_back();
            st[num]=0;
        }
    }
}
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<bool>st(n,false);
        vector<vector<int>>res;
        st[0]=true;
        init();
        dfs(0,graph,st,res);
        return res;
    }
};