Untitled
unknown
plain_text
3 years ago
1.7 kB
8
Indexable
import java.util.ArrayList;
class Solution {
static class Edge{
int src;
int nbr;
boolean isVisited = false;
Edge(int u, int v){
src = u;
nbr = v;
}
}
public List<List<Integer>> allPathsSourceTarget(int[][] edges) {
ArrayList<Edge> [] graph = new ArrayList[edges.length];
boolean [] visited = new boolean[edges.length];
for(int i=0;i<edges.length;i++){
graph [i] = new ArrayList<>();
visited[i] = false;
}
for(int i=0;i<edges.length;i++){
for(int j=0;j<edges[i].length;j++){
graph[i].add(new Edge(i,edges[i][j]));
}
}
return isPath(graph,0,edges.length,visited,new ArrayList<>());
}
public List<List<Integer>> isPath(ArrayList<Edge> [] graph,int src,int dest,boolean [] visited, List<Integer> tempRes){
List<List<Integer>> res = new ArrayList<>();
if(src == dest){
tempRes.add(src);
res.add(tempRes);
System.out.println(tempRes);
return res;
}
visited[src] = true;
tempRes.add(src);
for(int i=0;i<graph[src].size();i++){
if(visited[graph[src].get(i).nbr] == false){
List<List<Integer>> temp = isPath(graph,graph[src].get(i).nbr,dest,visited,tempRes);
if(temp.size() != 0) {
res.addAll(temp);
}
}
}
visited[src] = false;
return res;
}
AA
// [[4,3,1],[3,2,4],[3],[4],[]]
// [[1,2],[3],[3],[]]
}
Editor is loading...