Open Tcdian opened 3 years ago
/**
* @param {number[][]} graph
* @return {number[][]}
*/
var allPathsSourceTarget = function(graph) {
const result = [];
const path = [];
const n = graph.length - 1;
dfs(0);
return result;
function dfs(position) {
path.push(position);
if (position === n) {
result.push([...path]);
}
const nextPositions = graph[position];
for (let i = 0; i < nextPositions.length; i++) {
dfs(nextPositions[i]);
}
path.pop();
}
};
function allPathsSourceTarget(graph: number[][]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const n = graph.length - 1;
dfs(0);
return result;
function dfs(position: number) {
path.push(position);
if (position === n) {
result.push([...path]);
}
const nextPositions = graph[position];
for (let i = 0; i < nextPositions.length; i++) {
dfs(nextPositions[i]);
}
path.pop();
}
};
797. All Paths From Source to Target
给一个有
n
个结点的有向无环图,找到所有从0
到n-1
的路径并输出(不要求按顺序)二维数组的第
i
个数组中的单元都表示有向图中i
号结点所能到达的下一些结点(译者注:有向图是有方向的,即规定了a→b
你就不能从b→a
)空就是没有下一个结点了。Example
Note
[2, 15]
内。