LCR 110

问题

例子

思路

使用dfs便利所有边

代码

class Solution {
public:vector<vector<int>> res;void deep(vector<vector<int>>& graph, int id, vector<int>& buf){if(id==graph.size()-1){res.push_back(buf);return;}for(int i=0; i<graph[id].size(); i++){buf.push_back(graph[id][i]);deep(graph, graph[id][i], buf);buf.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {/*graph 是一个二维数组，[[1,2], [3], [3], []]表示0th 可以到达[1,2], 1th 可以到达[3], 2th 可以到达[3], 3th 是终点*/int n_var = graph.size()-1;vector<int> buf;buf.push_back(0);deep(graph,0, buf);return res;}
};

分析

空间复杂度：
O(n)

时间复杂度：
S = n*(1 + n)/2 = n*(n + 1)/2 = n +(n-1) + … + 1
时间复杂度应该是0(n^2)
边的数量是n * (n+1) /2