Author: Ashmit Mishra
Tester: Vipul Jain
Editorial: Manish Agrahari
Difficulty:
Medium
Prerequisite:
Queue, Breadth First Search, ArrayList
Explanation & Algorithm:
The park can be described as a graph with spots as vertices and paths as edges.
In this question we are given four types of input: -
The first one is n, the number of spots.
The second one is m, the number of paths.
The next m lines contain the indices of the spots that are connected.
Then, after m inputs a line containing two integers is given denoting the starting and the
ending spot.
To solve this question, store the indices of the connected spots in a 2D array of mx2.
Now pass this 2D array along with n, start and end into a function named “check”.In this
function we will create an adjacency list for the connected spots and then create a
boolean array visited of size n and then apply Breadth First Search.
If the check function returns true then we will print “Possible”, if the check function
returns false then we will print “Not Possible”.
Solution
Setter's Code
import java.util.*;
public class Main {
public boolean check(int n, int[][] edges, int start, int end) {
ArrayList<ArrayList> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(i, new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
adj.get(edges[i][0]).add(edges[i][1]);
adj.get(edges[i][1]).add(edges[i][0]);
}
boolean[] visited = new boolean[n];
return getPath(start, end, visited,adj);
}
public boolean getPath(int start, int end, boolean[]
visited,ArrayList<ArrayList> adj){
Queue q = new LinkedList<>();
q.add(start);
visited[start] = true;
while (!q.isEmpty()) {
int num1 = q.poll();
int i = 0;
while (i < adj.get(num1).size()) {
int num2 = adj.get(num1).get(i);
if (num2 == end) {
return true;
}
if (visited[num2] == false) {
q.add(num2);
visited[num2] = true;
}
i++;
}
}
return false;
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int a[][] = new int[m][2];
for(int i=0;i<m;i++){
int x = sc.nextInt();
int y = sc.nextInt();
a[i][0] = x;
a[i][1] = y;
}
int start = sc.nextInt();
int end = sc.nextInt();
Main obj = new Main();
boolean b = obj.check(n,a,start,end);
if(b==true){
System.out.println(“Possible”);
}
else{
System.out.println(“Not Possible”);
}
sc.close();
}
}
Tester's Code
#include <bits/stdc++.h>
using namespace std;
bool explore(vector<vector> &graph, int beg, int end, vector &visited)
{
if (beg == end){
return true;
}
else if (visited[beg]){
return false;
}
for (int i = 0; i < graph[beg].size(); i++)
{
visited[beg] = 1;
bool res = explore(graph, graph[beg][i], end, visited);
if (res){
return true;
}
}
return false;
}
bool check(int n, vector<vector> &edges, int start, int end)
{
vector<vector> graph(n);
vector visited(n, 0);
for (int i = 0; i < edges.size(); i++)
{
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
return explore(graph, start, end, visited);
}
int main()
{
int n, m;
cin >> n;
cin >> m;
vector<vector> adj;
int x, y;
for (int i = 0; i < m; i++)
{
vector temp;
cin >> x >> y;
temp.push_back(x);
temp.push_back(y);
adj.push_back(temp);
}
int start, end;
cin >> start >> end;
int b = check(n, adj, start, end);
if (b == 0)
{
cout << “Not Possible”;
}
else
{
cout << “Possible”;
}
}