Given an undirected graph, the task is to count the maximum number of Bridges between any two vertices of the given graph.
Examples:
Input:
Graph
1 ------- 2 ------- 3 -------- 4
| |
| |
5 ------- 6
Output: 2
Explanation:
There are 2 bridges, (1 - 2)
and (3 - 4), in the path from 1 to 4.
Input:
Graph:
1 ------- 2 ------- 3 ------- 4
Output: 3
Explanation:
There are 3 bridges, (1 - 2), (2 - 3)
and (3 - 4) in the path from 1 to 4.
Approach:
Follow the steps below to solve the problem:
- Find all the bridges in the graph and store them in a vector.
- Removal of all the bridges reduces the graph to small components.
- These small components do not have any bridges, and they are weakly connected components that do not contain bridges in them.
- Generate a tree consisting of the nodes connected by bridges, with the bridges as the edges.
- Now, the maximum bridges in a path between any node are equal to the diameter of this tree.
- Hence, find the diameter of this tree and print it as the answer.
Below is the implementation of the above approach
C++
// C++ program to find the// maximum number of bridges// in any path of the given graph#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5;// Stores the nodes// and their connectionsvector<vector<int> > v(N);// Store the tree with// Bridges as the edgesvector<vector<int> > g(N);// Stores the visited nodesvector<bool> vis(N, 0);// for finding bridgesvector<int> in(N), low(N);// for Disjoint Set Unionvector<int> parent(N), rnk(N);// for storing actual bridgesvector<pair<int, int> > bridges;// Stores the number of// nodes and edgesint n, m;// For finding bridgesint timer = 0;int find_set(int a){ // Function to find root of // the component in which // A lies if (parent[a] == a) return a; // Doing path compression return parent[a] = find_set(parent[a]);}void union_set(int a, int b){ // Function to do union // between a and b int x = find_set(a), y = find_set(b); // If both are already in the // same component if (x == y) return; // If both have same rank, // then increase anyone's rank if (rnk[x] == rnk[y]) rnk[x]++; if (rnk[y] > rnk[x]) swap(x, y); parent[y] = x;}// Function to find bridgesvoid dfsBridges(int a, int par){ vis[a] = 1; // Initialize in time and // low value in[a] = low[a] = timer++; for (int i v[a]) { if (i == par) continue; if (vis[i]) // Update the low value // of the parent low[a] = min(low[a], in[i]); else { // Perform DFS on its child // updating low if the child // has connection with any // ancestor dfsBridges(i, a); low[a] = min(low[a], low[i]); if (in[a] < low[i]) // Bridge found bridges.push_back(make_pair(i, a)); // Otherwise else // Find union between parent // and child as they // are in same component union_set(i, a); } }}// Function to find diameter of the// tree for storing max two depth childint dfsDiameter(int a, int par, int& diameter){ int x = 0, y = 0; for (int i g[a]) { if (i == par) continue; int mx = dfsDiameter(i, a, diameter); // Finding max two depth // from its children if (mx > x) { y = x; x = mx; } else if (mx > y) y = mx; } // Update diameter with the // sum of max two depths diameter = max(diameter, x + y); // Return the maximum depth return x + 1;}// Function to find maximum// bridges between// any two nodesint findMaxBridges(){ for (int i = 0; i <= n; i++) { parent[i] = i; rnk[i] = 1; } // DFS to find bridges dfsBridges(1, 0); // If no bridges are found if (bridges.empty()) return 0; int head = -1; // Iterate over all bridges for (auto& i bridges) { // Find the endpoints int a = find_set(i.first); int b = find_set(i.second); // Generate the tree with // bridges as the edges g[a].push_back(b); g[b].push_back(a); // Update the head head = a; } int diameter = 0; dfsDiameter(head, 0, diameter); // Return the diameter return diameter;}// Driver Codeint main(){ /* Graph => 1 ---- 2 ---- 3 ---- 4 | | 5 ---- 6 */ n = 6, m = 6; v[1].push_back(2); v[2].push_back(1); v[2].push_back(3); v[3].push_back(2); v[2].push_back(5); v[5].push_back(2); v[5].push_back(6); v[6].push_back(5); v[6].push_back(3); v[3].push_back(6); v[3].push_back(4); v[4].push_back(4); int ans = findMaxBridges(); cout << ans << endl; return 0;} |
Java
// Java program to find the// maximum number of bridges// in any path of the given graphimport java.util.*;class GFG{static int N = (int)1e5 + 5;// Stores the nodes// and their connectionsstatic Vector<Integer> []v = new Vector[N];// Store the tree with// Bridges as the edgesstatic Vector<Integer> []g = new Vector[N];// Stores the visited nodesstatic boolean []vis = new boolean[N];// For finding bridgesstatic int []in = new int[N];static int []low = new int[N];// for Disjoint Set Unionstatic int []parent = new int[N];static int []rnk = new int[N]; // For storing actual bridgesstatic Vector<pair> bridges = new Vector<>();// Stores the number of// nodes and edgesstatic int n, m; // For finding bridgesstatic int timer = 0;static int diameter; static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } static void swap(int x, int y) { int temp = x; x = y; y = temp;}static int find_set(int a){ // Function to find root of // the component in which // A lies if (parent[a] == a) return a; // Doing path compression return parent[a] = find_set(parent[a]);}static void union_set(int a, int b){ // Function to do union // between a and b int x = find_set(a), y = find_set(b); // If both are already // in the same component if (x == y) return; // If both have same rank, // then increase anyone's rank if (rnk[x] == rnk[y]) rnk[x]++; if (rnk[y] > rnk[x]) swap(x, y); parent[y] = x;}// Function to find bridgesstatic void dfsBridges(int a, int par){ vis[a] = true; // Initialize in time and // low value in[a] = low[a] = timer++; for (int i : v[a]) { if (i == par) continue; if (vis[i]) // Update the low value // of the parent low[a] = Math.min(low[a], in[i]); else { // Perform DFS on its child // updating low if the child // has connection with any // ancestor dfsBridges(i, a); low[a] = Math.min(low[a], low[i]); if (in[a] < low[i]) // Bridge found bridges.add(new pair(i, a)); // Otherwise else // Find union between parent // and child as they // are in same component union_set(i, a); } }}// Function to find diameter // of the tree for storing // max two depth childstatic int dfsDiameter(int a, int par){ int x = 0, y = 0; for (int i : g[a]) { if (i == par) continue; int mx = dfsDiameter(i, a); // Finding max two depth // from its children if (mx > x) { y = x; x = mx; } else if (mx > y) y = mx; } // Update diameter with the // sum of max two depths diameter = Math.max(diameter, x + y); // Return the maximum depth return x + 1;}// Function to find maximum// bridges between// any two nodesstatic int findMaxBridges(){ for (int i = 0; i <= n; i++) { parent[i] = i; rnk[i] = 1; } // DFS to find bridges dfsBridges(1, 0); // If no bridges are found if (bridges.isEmpty()) return 0; int head = -1; // Iterate over all bridges for (pair i : bridges) { // Find the endpoints int a = find_set(i.first); int b = find_set(i.second); // Generate the tree with // bridges as the edges g[a].add(b); g[b].add(a); // Update the head head = a; } diameter = 0; dfsDiameter(head, 0); // Return the diameter return diameter;}// Driver Codepublic static void main(String[] args){ /* Graph => 1 ---- 2 ---- 3 ---- 4 | | 5 ---- 6 */ n = 6; m = 6; for (int i = 0; i < v.length; i++) v[i] = new Vector<Integer>(); for (int i = 0; i < g.length; i++) g[i] = new Vector<Integer>(); v[1].add(2); v[2].add(1); v[2].add(3); v[3].add(2); v[2].add(5); v[5].add(2); v[5].add(6); v[6].add(5); v[6].add(3); v[3].add(6); v[3].add(4); v[4].add(4); int ans = findMaxBridges(); System.out.print(ans + "\n");}}// This code is contributed by Princi Singh |
Python3
# Python3 program to find the# maximum number of bridges# in any path of the given graphN = 100005 # Stores the nodes# and their connectionsv = []# Store the tree with# Bridges as the edgesg = []# Stores the visited nodesvis = [False]*(N)# For finding bridgesIn = [0]*(N)low = [0]*(N)# for Disjoint Set Unionparent = [0]*(N)rnk = [0]*(N)# For storing actual bridgesbridges = []# Stores the number of# nodes and edgesn, m = 6, 6# For finding bridgestimer = 0diameter = 0def swap(x, y): temp = x x = y y = tempdef find_set(a): global N, v, g, vis, In, low, parent, rnk, bridges, n, m, timer, diameter # Function to find root of # the component in which # A lies if parent[a] == a: return a # Doing path compression parent[a] = find_set(parent[a]) return parent[a]def union_set(a, b): global N, v, g, vis, In, low, parent, rnk, bridges, n, m, timer, diameter # Function to do union # between a and b x, y = find_set(a), find_set(b) # If both are already # in the same component if x == y: return # If both have same rank, # then increase anyone's rank if rnk[x] == rnk[y]: rnk[x]+=1 if rnk[y] > rnk[x]: swap(x, y) parent[y] = x# Function to find bridgesdef dfsBridges(a, par): global N, v, g, vis, In, low, parent, rnk, bridges, n, m, timer, diameter vis[a] = True # Initialize in time and # low value timer += 1 In[a], low[a] = timer, timer for i in range(len(v[a])): if v[a][i] == par: continue if vis[v[a][i]]: # Update the low value # of the parent low[a] = min(low[a], In[v[a][i]]) else: # Perform DFS on its child # updating low if the child # has connection with any # ancestor dfsBridges(v[a][i], a) low[a] = min(low[a], low[v[a][i]]) if In[a] < low[v[a][i]]: # Bridge found bridges.append([v[a][i], a]) # Otherwise else: # Find union between parent # and child as they # are in same component union_set(v[a][i], a)# Function to find diameter# of the tree for storing# max two depth childdef dfsDiameter(a, par): global N, v, g, vis, In, low, parent, rnk, bridges, n, m, timer, diameter x, y = 0, 0 for i in range(len(g[a])): if g[a][i] == par: continue mx = dfsDiameter(g[a][i], a) # Finding max two depth # from its children if mx > x: y = x x = mx elif mx > y: y = mx # Update diameter with the # sum of max two depths diameter = max(diameter, x + y) # Return the maximum depth return x + 1# Function to find maximum# bridges between# any two nodesdef findMaxBridges(): global N, v, g, vis, In, low, parent, rnk, bridges, n, m, timer, diameter for i in range(n + 1): parent[i] = i rnk[i] = 1 # DFS to find bridges dfsBridges(1, 0); # If no bridges are found if len(bridges) == 0: return 0 head = -1 # Iterate over all bridges for i in range(len(bridges)): # Find the endpoints a = find_set(bridges[i][0]) b = find_set(bridges[i][1]) # Generate the tree with # bridges as the edges g[a].append(b) g[b].append(a) # Update the head head = a diameter = 0 dfsDiameter(head, 0) # Return the diameter return diameter""" Graph => 1 ---- 2 ---- 3 ---- 4 | | 5 ---- 6"""for i in range(N): v.append([])for i in range(N): g.append([])v[1].append(2)v[2].append(1)v[2].append(3)v[3].append(2)v[2].append(5)v[5].append(2)v[5].append(6)v[6].append(5)v[6].append(3)v[3].append(6)v[3].append(4)v[4].append(4)ans = findMaxBridges()print(ans)# This code is contributed by suresh07. |
C#
// C# program to find the// maximum number of bridges// in any path of the given graphusing System;using System.Collections.Generic;class GFG{static int N = (int)1e5 + 5;// Stores the nodes// and their connectionsstatic List<int> []v = new List<int>[N];// Store the tree with// Bridges as the edgesstatic List<int> []g = new List<int>[N];// Stores the visited nodesstatic bool []vis = new bool[N];// For finding bridgesstatic int []init = new int[N];static int []low = new int[N];// for Disjoint Set Unionstatic int []parent = new int[N];static int []rnk = new int[N]; // For storing actual bridgesstatic List<pair> bridges = new List<pair>();// Stores the number of// nodes and edgesstatic int n, m; // For finding bridgesstatic int timer = 0;static int diameter; class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } static void swap(int x, int y) { int temp = x; x = y; y = temp;}static int find_set(int a){ // Function to find root of // the component in which // A lies if (parent[a] == a) return a; // Doing path compression return parent[a] = find_set(parent[a]);}static void union_set(int a, int b){ // Function to do union // between a and b int x = find_set(a), y = find_set(b); // If both are already // in the same component if (x == y) return; // If both have same rank, // then increase anyone's rank if (rnk[x] == rnk[y]) rnk[x]++; if (rnk[y] > rnk[x]) swap(x, y); parent[y] = x;}// Function to find bridgesstatic void dfsBridges(int a, int par){ vis[a] = true; // Initialize in time and // low value init[a] = low[a] = timer++; foreach (int i in v[a]) { if (i == par) continue; if (vis[i]) // Update the low value // of the parent low[a] = Math.Min(low[a], init[i]); else { // Perform DFS on its child // updating low if the child // has connection with any // ancestor dfsBridges(i, a); low[a] = Math.Min(low[a], low[i]); if (init[a] < low[i]) // Bridge found bridges.Add(new pair(i, a)); // Otherwise else // Find union between parent // and child as they // are in same component union_set(i, a); } }}// Function to find diameter // of the tree for storing // max two depth childstatic int dfsDiameter(int a, int par){ int x = 0, y = 0; foreach (int i in g[a]) { if (i == par) continue; int mx = dfsDiameter(i, a); // Finding max two depth // from its children if (mx > x) { y = x; x = mx; } else if (mx > y) y = mx; } // Update diameter with the // sum of max two depths diameter = Math.Max(diameter, x + y); // Return the // maximum depth return x + 1;}// Function to find maximum// bridges between// any two nodesstatic int findMaxBridges(){ for (int i = 0; i <= n; i++) { parent[i] = i; rnk[i] = 1; } // DFS to find bridges dfsBridges(1, 0); // If no bridges are found if (bridges.Count == 0) return 0; int head = -1; // Iterate over all bridges foreach (pair i in bridges) { // Find the endpoints int a = find_set(i.first); int b = find_set(i.second); // Generate the tree with // bridges as the edges g[a].Add(b); g[b].Add(a); // Update the head head = a; } diameter = 0; dfsDiameter(head, 0); // Return the diameter return diameter;}// Driver Codepublic static void Main(String[] args){ /* Graph => 1 ---- 2 ---- 3 ---- 4 | | 5 ---- 6 */ n = 6; m = 6; for (int i = 0; i < v.Length; i++) v[i] = new List<int>(); for (int i = 0; i < g.Length; i++) g[i] = new List<int>(); v[1].Add(2); v[2].Add(1); v[2].Add(3); v[3].Add(2); v[2].Add(5); v[5].Add(2); v[5].Add(6); v[6].Add(5); v[6].Add(3); v[3].Add(6); v[3].Add(4); v[4].Add(4); int ans = findMaxBridges(); Console.Write(ans + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program to find the // maximum number of bridges // in any path of the given graph let N = 1e5 + 5; // Stores the nodes // and their connections let v = new Array(N); // Store the tree with // Bridges as the edges let g = new Array(N); // Stores the visited nodes let vis = new Array(N); // For finding bridges let In = new Array(N); let low = new Array(N); // for Disjoint Set Union let parent = new Array(N); let rnk = new Array(N); // For storing actual bridges let bridges = []; // Stores the number of // nodes and edges let n, m; // For finding bridges let timer = 0; let diameter; function swap(x, y) { let temp = x; x = y; y = temp; } function find_set(a) { // Function to find root of // the component in which // A lies if (parent[a] == a) return a; // Doing path compression return parent[a] = find_set(parent[a]); } function union_set(a, b) { // Function to do union // between a and b let x = find_set(a), y = find_set(b); // If both are already // in the same component if (x == y) return; // If both have same rank, // then increase anyone's rank if (rnk[x] == rnk[y]) rnk[x]++; if (rnk[y] > rnk[x]) swap(x, y); parent[y] = x; } // Function to find bridges function dfsBridges(a, par) { vis[a] = true; // Initialize in time and // low value In[a] = low[a] = timer++; for (let i = 0; i < v[a].length; i++) { if (v[a][i] == par) continue; if (vis[v[a][i]]) // Update the low value // of the parent low[a] = Math.min(low[a], In[v[a][i]]); else { // Perform DFS on its child // updating low if the child // has connection with any // ancestor dfsBridges(v[a][i], a); low[a] = Math.min(low[a], low[v[a][i]]); if (In[a] < low[v[a][i]]) // Bridge found bridges.push([v[a][i], a]); // Otherwise else // Find union between parent // and child as they // are in same component union_set(v[a][i], a); } } } // Function to find diameter // of the tree for storing // max two depth child function dfsDiameter(a, par) { let x = 0, y = 0; for (let i = 0; i < g[a].length; i++) { if (g[a][i] == par) continue; let mx = dfsDiameter(g[a][i], a); // Finding max two depth // from its children if (mx > x) { y = x; x = mx; } else if (mx > y) y = mx; } // Update diameter with the // sum of max two depths diameter = Math.max(diameter, x + y); // Return the maximum depth return x + 1; } // Function to find maximum // bridges between // any two nodes function findMaxBridges() { for (let i = 0; i <= n; i++) { parent[i] = i; rnk[i] = 1; } // DFS to find bridges dfsBridges(1, 0); // If no bridges are found if (bridges.length == 0) return 0; let head = -1; // Iterate over all bridges for (let i = 0; i < bridges.length; i++) { // Find the endpoints let a = find_set(bridges[i][0]); let b = find_set(bridges[i][1]); // Generate the tree with // bridges as the edges g[a].push(b); g[b].push(a); // Update the head head = a; } diameter = 0; dfsDiameter(head, 0); // Return the diameter return diameter; } /* Graph => 1 ---- 2 ---- 3 ---- 4 | | 5 ---- 6 */ n = 6; m = 6; for (let i = 0; i < v.length; i++) v[i] = []; for (let i = 0; i < g.length; i++) g[i] = []; v[1].push(2); v[2].push(1); v[2].push(3); v[3].push(2); v[2].push(5); v[5].push(2); v[5].push(6); v[6].push(5); v[6].push(3); v[3].push(6); v[3].push(4); v[4].push(4); let ans = findMaxBridges(); document.write(ans + "</br>");// This code is contributed by mukesh07.</script> |
Output:
2
Time Complexity: O(N + M)
Auxiliary Space: O(N + M)
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!
