Untitled

 avatar
unknown
plain_text
2 years ago
1.7 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);
            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...