Find if there is a path between two vertices in a undirected graph
public class Solution {
public static boolean helper(int edges[][], int v1, int v2, boolean visited[]) {
int n = edges.length;
visited[v1] = true;
for (int i = 0; i < n; i++) {
if (edges[v1][i] == 1 && i == v2)
return true;
else if (edges[v1][i] == 1 && !visited[i])
if (helper(edges, i, v2, visited))
return true;
}
return false;
}
public static boolean isReachable(int edges[][], int v1, int v2) {
boolean[] visited = new boolean[edges.length];
return helper(edges, v1, v2, visited);
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int V = s.nextInt();
int E = s.nextInt();
int edges[][] = new int[V][V];
for (int i = 0; i < E; i++) {
int fv = s.nextInt();
int sv = s.nextInt();
edges[sv][fv] = 1;
edges[fv][sv] = 1;
}
int v1 = s.nextInt();
int v2 = s.nextInt();
System.out.println(isReachable(edges, v1, v2));
}
}
Last updated