Given an undirected Connected graph of V vertices and E edges. A critical connection is an edge that, if removed, will make some nodes unable to reach some other nodes, the task is to find all critical connections in the graph.
Note: There are many possible orders for the answer. You are supposed to print the edges in sorted order, and also an edge should be in sorted order too. So if there’s an edge between nodes 1 and 2, you should print it like (1,2) and not (2,1).
Examples:
Input:
Output: 0 1 0 2 Explanation: Both the edges in the graph are Crtical connections.
Input:
Output: 2 3 Explanation: The edge between nodes 2 and 3 is the only Critical connection in the given graph.
Approach: To solve the problem follow the below idea:
- An edge is a critical connection, if and only if it is not in a cycle.
- So, if we know how to find cycles, and discard all edges in the cycles, then the remaining connections are a complete collection of critical connections.
Follow the steps to solve the problem:
- Use DFS algorithm to decide whether an edge is in a cycle or not.
- Assign a rank or depth to each node while traversing using the dfs. As we keep moving into the depth in the dfs, if some how we jump to node which has lower depth and already visited this means a cycle is found and the edges present in this cycle is not critical connections.
- But only the current level of search knows it finds a cycle. How does the upper level of search knows, if you backtrack?
- Let’s make use of the return value of DFS:
dfs
function returns the minimum rank it finds. During a step of search from nodeu
to its neighborv
, ifdfs(v)
returns something smaller than or equal torank(u)
, thenu
knows its neighborv
helped it to find a cycle back tou
oru
‘s ancestor. Sou
knows it should discard the edge(u, v)
which is in a cycle.
- Let’s make use of the return value of DFS:
Below is the Implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int dfs( int i, int p, vector< int >& rank, int k, vector< int > adj[], vector<vector< int > >& ans, vector< int >& vis) { // Set rank of the ith node to k // which is depth rank[i] = k; // Mark ith node as visited vis[i] = 1; int minDepth = INT_MAX; // Exploring all the neighbour // node of node i for ( auto ch : adj[i]) { // This if condition is to make // sure we do not call parent // from where it is called to // avoid child parent loop if (ch != p) { // If neighbour is already // visited then we take // minimum with rank of ch, // means a cycle is found if (vis[ch]) { minDepth = min(minDepth, rank[ch]); } // If neighbour is not // visited then we go in // depth to check cycle // is present or not else { int minRank = dfs(ch, i, rank, k + 1, adj, ans, vis); // If dfs returns smaller // depth value than current // depth it means current // edge is in a cycle // else there is no cycle // so we have pushed the // edge in our answer if (rank[i] < minRank) { ans.push_back({ i, ch }); } minDepth = min(minRank, minDepth); } } } return minDepth; } // Function to calculate // the critical edges vector<vector< int > > criticalConnections( int V, vector< int > adj[]) { vector<vector< int > > ans; vector< int > rank(V, -1), vis(V, 0); dfs(0, -1, rank, 0, adj, ans, vis); for ( int i = 0; i < ans.size(); i++) { sort(ans[i].begin(), ans[i].end()); } sort(ans.begin(), ans.end()); return ans; } // Drivers code int main() { int v = 3, e = 2; vector<vector< int > > edges = { { 0, 1 }, { 0, 2 } }; vector< int > adj[v]; for ( int i = 0; i < e; i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } vector<vector< int > > ans = criticalConnections(v, adj); sort(ans.begin(), ans.end()); for ( int i = 0; i < ans.size(); i++) { cout << ans[i][0] << " " << ans[i][1] << endl; } return 0; } |
Java
import java.util.*; public class Main { // Function to find critical connections in a graph static List<List<Integer>> criticalConnections( int V, List<Integer>[] adj) { List<List<Integer>> ans = new ArrayList<>(); int [] rank = new int [V]; Arrays.fill(rank, - 1 ); int [] vis = new int [V]; dfs( 0 , - 1 , rank, 0 , adj, ans, vis); // Sort each edge in ascending order of nodes for (List<Integer> edge : ans) { Collections.sort(edge); } // Sort the list of edges ans.sort((a, b) -> { if (a.get( 0 ).equals(b.get( 0 ))) { return a.get( 1 ) - b.get( 1 ); } return a.get( 0 ) - b.get( 0 ); }); return ans; } // Depth-first search to find critical connections static int dfs( int i, int p, int [] rank, int k, List<Integer>[] adj, List<List<Integer>> ans, int [] vis) { rank[i] = k; vis[i] = 1 ; int minDepth = Integer.MAX_VALUE; for ( int ch : adj[i]) { if (ch != p) { if (vis[ch] == 1 ) { minDepth = Math.min(minDepth, rank[ch]); } else { int minRank = dfs(ch, i, rank, k + 1 , adj, ans, vis); if (rank[i] < minRank) { List<Integer> edge = new ArrayList<>(); edge.add(i); edge.add(ch); ans.add(edge); } minDepth = Math.min(minRank, minDepth); } } } return minDepth; } public static void main(String[] args) { int V = 3 ; List<Integer>[] adj = new ArrayList[V]; for ( int i = 0 ; i < V; i++) { adj[i] = new ArrayList<>(); } List<List<Integer>> edges = new ArrayList<>(); edges.add(Arrays.asList( 0 , 1 )); edges.add(Arrays.asList( 0 , 2 )); for (List<Integer> edge : edges) { adj[edge.get( 0 )].add(edge.get( 1 )); adj[edge.get( 1 )].add(edge.get( 0 )); } List<List<Integer>> ans = criticalConnections(V, adj); // Print the critical connections for (List<Integer> edge : ans) { System.out.println(edge.get( 0 ) + " " + edge.get( 1 )); } } } |
Python3
# Python code for the above approach: def dfs(i, p, rank, k, adj, ans, vis): # Set rank of the ith node to k # which is depth rank[i] = k # Mark ith node as visited vis[i] = 1 minDepth = float ( 'inf' ) # Exploring all the neighbour # node of node i for ch in adj[i]: # This if condition is to make # sure we do not call parent # from where it is called to # avoid child parent loop if ch ! = p: # If neighbour is already # visited then we take # minimum with rank of ch, # means a cycle is found if vis[ch]: minDepth = min (minDepth, rank[ch]) # If neighbour is not # visited then we go in # depth to check cycle # is present or not else : minRank = dfs(ch, i, rank, k + 1 , adj, ans, vis) # If dfs returns smaller # depth value than current # depth it means current # edge is in a cycle # else there is no cycle # so we have pushed the # edge in our answer if rank[i] < minRank: ans.append([i, ch]) minDepth = min (minRank, minDepth) return minDepth # Function to calculate # the critical edges def criticalConnections(V, adj): ans = [] rank = [ - 1 ] * V vis = [ 0 ] * V dfs( 0 , - 1 , rank, 0 , adj, ans, vis) for i in range ( len (ans)): ans[i].sort() ans.sort() return ans # Drivers code v = 3 e = 2 edges = [[ 0 , 1 ], [ 0 , 2 ]] adj = [[] for _ in range (v)] for i in range (e): adj[edges[i][ 0 ]].append(edges[i][ 1 ]) adj[edges[i][ 1 ]].append(edges[i][ 0 ]) ans = criticalConnections(v, adj) ans.sort() for i in range ( len (ans)): print (ans[i][ 0 ], ans[i][ 1 ]) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; using System.Collections.Generic; class MainClass { // Function to find critical connections in a graph static List<List< int >> CriticalConnections( int V, List< int >[] adj) { List<List< int >> ans = new List<List< int >>(); int [] rank = new int [V]; for ( int i = 0; i < V; i++) { rank[i] = -1; } int [] vis = new int [V]; DFS(0, -1, rank, 0, adj, ans, vis); // Sort each edge in ascending order of nodes foreach ( var edge in ans) { edge.Sort(); } // Sort the list of edges ans.Sort((a, b) => { if (a[0] == b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }); return ans; } // Depth-first search to find critical connections static int DFS( int i, int p, int [] rank, int k, List< int >[] adj, List<List< int >> ans, int [] vis) { rank[i] = k; vis[i] = 1; int minDepth = int .MaxValue; foreach ( var ch in adj[i]) { if (ch != p) { if (vis[ch] == 1) { minDepth = Math.Min(minDepth, rank[ch]); } else { int minRank = DFS(ch, i, rank, k + 1, adj, ans, vis); if (rank[i] < minRank) { List< int > edge = new List< int > { i, ch }; ans.Add(edge); } minDepth = Math.Min(minRank, minDepth); } } } return minDepth; } public static void Main( string [] args) { int V = 3; List< int >[] adj = new List< int >[V]; for ( int i = 0; i < V; i++) { adj[i] = new List< int >(); } List<List< int >> edges = new List<List< int >> { new List< int > { |
Javascript
function criticalConnections(V, adj) { const ans = []; const rank = new Array(V).fill(-1); const vis = new Array(V).fill(0); // Depth-first search to find critical connections function dfs(i, p, k) { rank[i] = k; vis[i] = 1; let minDepth = Infinity; for (const ch of adj[i]) { if (ch !== p) { if (vis[ch] === 1) { minDepth = Math.min(minDepth, rank[ch]); } else { const minRank = dfs(ch, i, k + 1); if (rank[i] < minRank) { ans.push([i, ch]); } minDepth = Math.min(minRank, minDepth); } } } return minDepth; } dfs(0, -1, 0); // Sort each edge in ascending order of nodes ans.forEach(edge => { edge.sort((a, b) => a - b); }); // Sort the list of edges ans.sort((a, b) => { if (a[0] === b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }); return ans; } const V = 3; const adj = new Array(V).fill().map(() => []); const edges = [[0, 1], [0, 2]]; edges.forEach(edge => { adj[edge[0]].push(edge[1]); adj[edge[1]].push(edge[0]); }); const ans = criticalConnections(V, adj); // Print the critical connections ans.forEach(edge => { console.log(edge[0], edge[1]); }); |
0 1 0 2
Time Complexity: O(V) + ElogE
Auxiliary Space : O(V)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!