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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
