Untitled
unknown
plain_text
2 years ago
1.6 kB
5
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); 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; } }
Editor is loading...