Find if Path Exist in Graph

class Solution {
    
    static class Graph {
        private final List<List<Integer>> g;
        
        public Graph(int[][] edges, int n) {
            g = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                g.add(new ArrayList<>());
            }
            for(int[] edge: edges) {
                addEdge(edge[0], edge[1]);
            }
        }
        
        public void addEdge(int x, int y) {
            this.g.get(x).add(y);
            this.g.get(y).add(x);
        }
        
        public boolean isReachable(int s, int d) {
            if (s == d) {
                return true;
            }
            
            boolean[] visited = new boolean[g.size()];
            Stack<Integer> st = new Stack<>();
            visited[s] = true;
            st.push(s);
            while (!st.empty()) {
                int top = st.pop();
                for (int i = 0; i < this.g.get(top).size(); i++) {
                    int current = g.get(top).get(i);
                    if (current == d) {
                        return true;  
                    }
                    if (visited[current] != true) {
                        visited[current] = true;
                     st.push(current);
                    }
                }
            }
            return false;
            
        }
    }
    
    public boolean validPath(int n, int[][] edges, int start, int end) {
        Stack<Integer> s = new Stack<>();
        Graph g = new Graph(edges, n);
        return g.isReachable(start, end);    
    }
}

Last updated