1192. Critical Connections in a Network / Find Bridges

Problem Statement

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

Constraints:

• 2 <= n <= 105

• n - 1 <= connections.length <= 105

• 0 <= ai, bi <= n - 1

• ai != bi

• There are no repeated connections.

Intuition

Approach:

Maintain two arrays , start time and low(tracking lowest timre it can reach)
Traverse,

Whenever the low[adjacent node] > starttime[parent]  
    Bridge

Intuition is that,
    2
  /  \
1 ----3 -- 4
(start_time, low)
We start Dfs from 1(1,1) -> 2(2,2) -> 3(3,3) -> 2
Now we reach 2 but dfs over here, we update low of 3
Lowest 3 can be reach 2
3(3,2) -> 4(4,4)
Now low(4) > start[3] hence, it means 4 was visited at time 4
But 3 was visited at strating 3, can hence 4 cannot reach 3, hence bridge

Links

https://leetcode.com/problems/critical-connections-in-a-network/description/

Video Links

https://www.youtube.com/watch?v=qrAub5z8FeA

Approach 1:

C++

class Solution {
public:
    int timer=1;
    vector<vector<int>> bridges;
    vector<int> start, low;
    void dfs(int node, int parent, vector<bool> &visited, vector<int> adj[]){
        visited[node] = true;
        start[node] = timer;
        low[node] = timer;
        timer++;

        for(auto &it: adj[node]){
            if(it == parent)   
                continue;

            if(!visited[it]){
                dfs(it, node, visited, adj);
                low[node] = min(low[node], low[it]);
                if(low[it] > start[node])
                    bridges.push_back({it,node});

            }
            else{
                low[node] = min(low[node], low[it]);
            }
        } 
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<int> adj[n];
        start.resize(n);
        low.resize(n);
        vector<bool> visited(n, false);

        for(auto &it: connections){
            adj[it[0]].push_back(it[1]);
            adj[it[1]].push_back(it[0]);
        }

        dfs(0, -1, visited, adj);
        return bridges;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems