Minimum bridges required to be crossed to reach N
Given an integer N denoting the number of connected cities ( numbered from 1 to N ) and a 2D array arr[][] consisting of pairs connected to each other by bidirectional bridges. The task is to find the minimum the number of bridges required to be crossed to reach the city N from the city 1.
Examples:
Input: N = 3, M = 2, arr[][] = {{1, 2}, {2, 3}}
Output: 2
Explanation:
To reach Node 2 from Node 1, 1 bridge is required to be crossed.
To reach Node 3 from Node 2, 1 bridge is required to be crossed.
Hence, 2 bridges are required to be connected.Input: N = 4, M = 3, arr[][] = {{1, 2}, {2, 3}, {2, 4}}
Output: 2
Approach: Follow the steps below to solve the problem:
- Initialize an adjacency list to build and store the Graph nodes.
- Initialize an array, say vis[] of size N to mark the visited nodes and another array, say dist[] of size N, to store the minimum distance from city 1.
- Perform BFS and using the concept of Single Source Shortest Path to traverse the graph and store the minimum number of bridges required to be crossed to reach every city from city 1.
- Print the value of dist[N] as the minimum distance to reach city N from city 1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Adjacency list to store graphvector<int> g[10001];// Stores info about visited nodesint vis[10001];// Stores distance of nodes// from the source nodeint dist[10001];// Function for BFS traversalvoid BFS(int src){ // Stores the nodes queue<int> q; // Push the source node q.push(src); // Mark the pushed node visited vis[src] = 1; // Source node is always at dist 0 dist[src] = 0; // Iterate until queue is not empty while (!q.empty()) { // Update the current node int curr = q.front(); // Pop the node after // update by curr q.pop(); // Traverse every node of // the adjacency list for (auto child : g[curr]) { if (vis[child] == 0) { // Push the child node // if its not visited q.push(child); // Update the distance of next level // nodes as it can be accessed by the // previous node in BFS dist[child] = dist[curr] + 1; // Mark the child node as visited vis[child] = 1; } } }}// Function to build the graphvoid buildGraph(int M, int arr[][2]){ for (int i = 0; i < M; i++) { g[arr[i][0]].push_back(arr[i][1]); g[arr[i][1]].push_back(arr[i][0]); }}// Function to print the distance between from// city 1 to city Nvoid shortestDistance(int N, int M, int arr[][2]){ // Build graph buildGraph(M, arr); // Perform BFS traversal BFS(1); // Print the shortest distance cout << dist[N];}// Driver Codeint main(){ // Given number of Nodes & Edges int N = 3, M = 2; // Given pairs of edges int arr[][2] = { { 1, 2 }, { 2, 3 } }; // Function Call shortestDistance(N, M, arr);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Adjacency list to store graphstatic Vector<Integer> []g = new Vector[10001];// Stores info about visited nodesstatic int []vis = new int[10001];// Stores distance of nodes// from the source nodestatic int []dist = new int[10001];static { for(int i = 0; i < g.length; i++) { g[i] = new Vector<>(); }} // Function for BFS traversalstatic void BFS(int src){ // Stores the nodes Queue<Integer> q = new LinkedList<>(); // Push the source node q.add(src); // Mark the pushed node visited vis[src] = 1; // Source node is always at dist 0 dist[src] = 0; // Iterate until queue is not empty while (!q.isEmpty()) { // Update the current node int curr = q.peek(); // Pop the node after // update by curr q.remove(); // Traverse every node of // the adjacency list for (int child : g[curr]) { if (vis[child] == 0) { // Push the child node // if its not visited q.add(child); // Update the distance of next level // nodes as it can be accessed by the // previous node in BFS dist[child] = dist[curr] + 1; // Mark the child node as visited vis[child] = 1; } } }}// Function to build the graphstatic void buildGraph(int M, int arr[][]){ for (int i = 0; i < M; i++) { g[arr[i][0]].add(arr[i][1]); g[arr[i][1]].add(arr[i][0]); }}// Function to print the distance between from// city 1 to city Nstatic void shortestDistance(int N, int M, int arr[][]){ // Build graph buildGraph(M, arr); // Perform BFS traversal BFS(1); // Print the shortest distance System.out.print(dist[N]);}// Driver Codepublic static void main(String[] args){ // Given number of Nodes & Edges int N = 3, M = 2; // Given pairs of edges int arr[][] = { { 1, 2 }, { 2, 3 } }; // Function Call shortestDistance(N, M, arr);}}// This code is contributed by shikhasingrajput. |
Python3
# Python 3 program for the above approach# Adjacency list to store graphg = [[] for i in range(10001)]# Stores info about visited nodesvis = [0 for i in range(10001)]# Stores distance of nodes# from the source nodedist = [0 for i in range(10001)]# Function for BFS traversaldef BFS(src): global vis global dist global g # Stores the nodes q = [] # Push the source node q.append(src) # Mark the pushed node visited vis[src] = 1 # Source node is always at dist 0 dist[src] = 0 # Iterate until queue is not empty while (len(q)): # Update the current node curr = q[0] # Pop the node after # update by curr q.remove(q[0]) # Traverse every node of # the adjacency list for child in g[curr]: if (vis[child] == 0): # Push the child node # if its not visited q.append(child) # Update the distance of next level # nodes as it can be accessed by the # previous node in BFS dist[child] = dist[curr] + 1 # Mark the child node as visited vis[child] = 1# Function to build the graphdef buildGraph(M, arr): global g for i in range(M): g[arr[i][0]].append(arr[i][1]) g[arr[i][1]].append(arr[i][0])# Function to print the distance between from# city 1 to city Ndef shortestDistance(N, M, arr): # Build graph buildGraph(M, arr) # Perform BFS traversal BFS(1) # Print the shortest distance print(dist[N])# Driver Codeif __name__ == '__main__': # Given number of Nodes & Edges N = 3 M = 2 # Given pairs of edges arr = [[1, 2], [2, 3]] # Function Call shortestDistance(N, M, arr) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Adjacency list to store graphstatic List<int> []g = new List<int>[10001];// Stores info about visited nodesstatic int []vis = new int[10001];// Stores distance of nodes// from the source nodestatic int []dist = new int[10001]; // Function for BFS traversalstatic void BFS(int src){ // Stores the nodes Queue<int> q = new Queue<int>(); // Push the source node q.Enqueue(src); // Mark the pushed node visited vis[src] = 1; // Source node is always at dist 0 dist[src] = 0; // Iterate until queue is not empty while (q.Count!=0) { // Update the current node int curr = q.Peek(); // Pop the node after // update by curr q.Dequeue(); // Traverse every node of // the adjacency list foreach (int child in g[curr]) { if (vis[child] == 0) { // Push the child node // if its not visited q.Enqueue(child); // Update the distance of next level // nodes as it can be accessed by the // previous node in BFS dist[child] = dist[curr] + 1; // Mark the child node as visited vis[child] = 1; } } }}// Function to build the graphstatic void buildGraph(int M, int [,]arr){ for (int i = 0; i < M; i++) { g[arr[i,0]].Add(arr[i,1]); g[arr[i,1]].Add(arr[i,0]); }}// Function to print the distance between from// city 1 to city Nstatic void shortestDistance(int N, int M, int [,]arr){ // Build graph buildGraph(M, arr); // Perform BFS traversal BFS(1); // Print the shortest distance Console.Write(dist[N]);}// Driver Codepublic static void Main(String[] args){ // Given number of Nodes & Edges int N = 3, M = 2; // Given pairs of edges int [,]arr = { { 1, 2 }, { 2, 3 } }; for(int i = 0; i < g.Length; i++) { g[i] = new List<int>(); } // Function Call shortestDistance(N, M, arr);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Adjacency list to store graphvar g = Array.from(Array(10001), ()=>new Array());;// Stores info about visited nodesvar vis = Array(10001).fill(false);// Stores distance of nodes// from the source nodevar dist = Array(10001).fill(0);// Function for BFS traversalfunction BFS(src){ // Stores the nodes var q = []; // Push the source node q.push(src); // Mark the pushed node visited vis[src] = 1; // Source node is always at dist 0 dist[src] = 0; // Iterate until queue is not empty while (q.length!=0) { // Update the current node var curr = q[0]; // Pop the node after // update by curr q.shift(); // Traverse every node of // the adjacency list g[curr].forEach(child => { if (vis[child] == 0) { // Push the child node // if its not visited q.push(child); // Update the distance of next level // nodes as it can be accessed by the // previous node in BFS dist[child] = dist[curr] + 1; // Mark the child node as visited vis[child] = 1; } }); }}// Function to build the graphfunction buildGraph(M, arr){ for (var i = 0; i < M; i++) { g[arr[i][0]].push(arr[i][1]); g[arr[i][1]].push(arr[i][0]); }}// Function to print the distance between from// city 1 to city Nfunction shortestDistance(N, M, arr){ // Build graph buildGraph(M, arr); // Perform BFS traversal BFS(1); // Print the shortest distance document.write( dist[N]);}// Driver Code// Given number of Nodes & Edgesvar N = 3, M = 2;// Given pairs of edgesvar arr = [ [ 1, 2 ], [ 2, 3 ] ];// Function CallshortestDistance(N, M, arr);</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
