Monk and the Islands HackerEarth Solution and Explanation

Monk and the Islands HackerEarth Solution and Explanation

2 min read

Monk visits the land of 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 the Island #N. Find the minimum number of bridges that he shall have to cross if he takes the optimal route.

Input:
First line contains TT testcases follow.
First line of each test case contains two space-separated integers NM.
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, YN

Sample Input:

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

Sample Output:

2
2

Solution in c++

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector <int> adj[1000000];
int dist[10001], visted[100000];

void BFS(int src){
	queue <int> q;
	q.push(src);
	visted[src] = 1;
	dist[src] = 0;
       
        // While loop till queue became empty i.e BFS Operation
	while(!q.empty()) {
        // store the value of first element of queue into current node value
	int current = q.front();
	q.pop();

	for(int child: adj[current]){
	if(visted[child] ==0){
		q.push(child);
		dist[child] = dist[current] + 1;
		visted[child] = 1;
	}
        }
	} 
}

int main(){
	int t,N,M,X,Y;
    cin>>t;
	while(t--){
		
		cin>>N>>M;
		for(int i =1;i<=N;i++) adj[i].clear(), visted[i] = 0;
		for(int i = 0;i<M;i++){
             cin>>X>>Y;
			adj[X].push_back(Y);
			adj[Y].push_back(X);
		}

		BFS(1);	
		cout<<dist[N]<<endl;
	}
}

Solution on Youtube

Tags: , ,
Choose your Reaction!
Leave a Comment