Prerequisite :- Graph,Bfs
Problem:- The hero wants to travel from building S to T. Given M pairs of buildings through which the hero can jump, determine whether the hero can reach building T and the minimum number of jumps required. If the hero can’t reach building T, print zero.
Explanation :-
- BFS is a graph algorithm required to solve this problem. This algorithm usually helps us find the minimum distance between two points. In this algorithm, we iterate over all the adjacent vertices of our source vertex, and then we continue iterating over adjacent vertices level by level until we reach the destination vertex.
- Start a BFS from building S and calculate the shortest distance to building T through BFS. If your BFS doesn’t reach building T, print 0.
Example : -
Given test case
5 5
1 3
2 3
1 2
3 5
4 5
1 4
Starting from vertice 1 which is your S point and 4 is your T point.
Zero level :- 1
First level :- 3 2
Second level :- 5
Third level :- 4
C++ Solution :-
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int n, m;
cin >> n >> m;
vector < int > adj[n + 1];
for (int i = 0; i < m; i++) {
int n1, n2;
cin >> n1 >> n2;
adj[n1].push_back(n2);
adj[n2].push_back(n1);
}
int source, destination;
cin >> source >> destination;
vector < bool > vis(n + 1, false);
queue < int > q1;
q1.push(source);
int cnt = 0;
vis[source] = true;
bool judge = false;
while (q1.size() != 0) {
int n = q1.size();
for (int i = 0; i < n; i++) {
int val = q1.front();
q1.pop();
if (val == destination) {
judge = true;
break;
}
for (auto e: adj[val]) {
if (vis[e] == false) {
q1.push(e);
vis[e] = true;
}
}
}
if (judge) break;
cnt++;
}
if (judge == false) {
cout << 0 << "\n";
} else {
cout << cnt << "\n";
}
}