Has Path

https://leetcode.com/problems/find-if-path-exists-in-graph/

I/P:

7

8

0 1 10

1 2 10

2 3 10

0 3 10

3 4 10

4 5 10

5 6 10

4 6 10

0

6

O/P: true

I/P:

7

7

0 1 10

0 3 10

1 2 10

2 3 10

4 5 10

4 6 10

5 6 10

0

4

O/P: false

package pep.Day38;

import java.io.*;
import java.util.*;

public class Has_Path {
    static class Edge {
        int src;
        int nbr;
        int wt;

        Edge(int src, int nbr, int wt) {
            this.src = src;
            this.nbr = nbr;
            this.wt = wt;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            int wt = Integer.parseInt(parts[2]);
            graph[v1].add(new Edge(v1, v2, wt));
            graph[v2].add(new Edge(v2, v1, wt));
        }

        int src = Integer.parseInt(br.readLine());
        int dest = Integer.parseInt(br.readLine());

        // write your code here
        boolean[] visited = new boolean[vtces];
        System.out.println(hasPath(graph, src, dest, visited));
    }

    public static boolean hasPath(ArrayList<Edge>[] graph, int src, int dest, boolean[] visited) {
        if (src == dest) {
            return true;
        }
        visited[src] = true;
        for (Edge e : graph[src]) {
            if (!visited[e.nbr]) {
                if (hasPath(graph, e.nbr, dest, visited))
                    return true;
            }
        }
        visited[src] = false;
        return false;
    }

}

Time Complexity: O(V+E)

Where V is the number of vertices and E is the number of edges. In the worst case, all the vertices and all the edges will be travelled. The time complexity of the while loop (k log(k)).Which sum up to O(n log(k)).

Space Complexity: O(V)

It will be the height of the recursion stack, which can be O(V) at max