Monk and the Islands-HackerEarth(Graph)

Prerequisite:- Graph, shortest path using BFS , Dijkstra

Monk visits the land of the Islands. There are a total of N islands numbered from 1 to N. Some pairs of islands are connected to each other by Bidirectional bridges running over water.
Monk hates to cross these bridges as they require a lot of effort. He is standing at Island #1 and wants to reach Island #N. Find the minimum number of bridges that he shall have to cross if he takes the optimal route.

Input:
First-line contains T. T test cases follow.
The first line of each test case contains two space-separated integers N, M.
Each of the next M lines contains two space-separated integers X and Y, denoting that there is a bridge between Island X and Island Y.

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 104
1 ≤ M ≤ 105
1 ≤ X, Y ≤ N

Sample Input

2
3 2
1 2
2 3
4 4
1 2
2 3
3 4
4 2

Sample Output

2
2

Java Solution :-

import java.util.*;

import java.io.*;

import java.lang.*;

class TestClass {

static ArrayList<Integer> adj[];

static class Graph{

static int v ;

Graph(int v)

{

this.v = v;

adj = new ArrayList[v+1];

for(int i = 1 ; i < v+1 ; i++)

{

adj[i] = new ArrayList<Integer>();

}

}

static void bfs(int[] visited ,int[] dist , int i )

{

visited[i] = 1 ;

Queue<Integer> q = new LinkedList<>();

dist[i] = 0;

q.add(i);

while(!q.isEmpty())

{

int curr = q.poll();

for(int child : adj[curr])

{

if(visited[child] == 0 )

{

visited[child] = 1 ;

q.add(child);

dist[child] = dist[curr ] + 1 ;

}

}

}

}

}

public static void main(String args[] ) throws Exception {

// Scanner

Scanner sc = new Scanner(System.in);

int test = sc.nextInt(); // Reading input from STDIN

// System.out.println(“Hi, “ + name + “.”); // Writing output to STDOUT

Graph g = new Graph(10001);

int visited[] = new int[10001];

int dist[] = new int[10001];

while(test → 0)

{

// int count = 0;

int n = sc.nextInt();

int m = sc.nextInt();

for(int i = 1 ; i <= n ; i++)

{

adj[i].clear();

visited[i] = 0;

}

for(int i = 1 ; i < m+1 ; i++)

{

int a = sc.nextInt();

int b = sc.nextInt();

adj[a].add(b);

adj[b].add(a);

}

g.bfs(visited ,dist ,1 );

System.out.println(dist[n] );

}

}

}