Critical Connections Problem

Given a network of servers where each server is connected to every other server directly or indirectly through the bidirectional connections in the network, find all the critical connections.

A connection in a connected network is said to be critical if removing it disconnects the network.

Example One

Input:

n =  5

connections = [

[0, 1],

[0, 2],

[0, 4],

[1, 2],

[1, 3]

]

Output: [

[0, 4],

[1, 3]

]

Example Two

Input:

n =  4

connections = [

[0, 1],

[0, 2],

[0, 3],

[1, 2],

[2, 3]

]

Output: [

[-1, -1]

]

Removal of any connection will not disconnect the network.

Notes

– Return [[-1,-1]] when there is no critical connection in the network.

Constraints:

• 1 <= number of servers <= 10^5
• 0 <= number of connections <= 10^5
• Servers are numbered from 0 to (number of servers – 1).
• There are no self-loops and multiple edges.

Solutions

We have provided two solutions.

We will start with a brute force approach first, later we will present an optimal solution.

Consider the servers as vertices and connections as edges of an undirected graph.

1) brute_force_solution.cpp

Remove all edges of the graph one at a time, and see if the removal of the edge creates a disconnected graph. The solution has the following steps:

For every edge e in the graph,

a. Remove e from the graph

b. See if the graph remains connected (by using BFS or DFS)

c. Add e back to the graph

Time complexity:

O(number_of_connections * (number_of_servers + number_of_connections))

To create adjacency list = O(number_of_connections).

To apply DFS/BFS for number_of_connections times algorithm = O(number_of_connections * (number_of_servers + number_of_connections)).

Auxiliary Space Used:

O(number_of_servers + number_of_connections).

Memory used for adjacency list = O(number_of_servers + number_of_connections).

Memory used for marking nodes in BFS = O(number_of_servers).

Memory used for recursion call stack (only for DFS) = O(number_of_servers).

Space Complexity:

O(number_of_servers + number_of_connections).

Memory used for input = O(number_of_connections).

Memory used for output = O(number_of_connections).

Auxiliary space = O(number_of_servers + number_of_connections).

Total space complexity = O(number_of_servers + number_of_connections).

// -------- START --------

vector<vector> adj_list;
vector visited;

// v --> The vertex to be visited next 
void dfs(int v) {
    visited[v] = true;

    for(int u : adj_list[v]){
        if(!visited[u])
            dfs(u);
    }
}

vector<vector> find_critical_connections(int number_of_servers, vector<vector> connections) {
    vector<vector> criticalConnections;

    for(int i = 0; i < connections.size(); i++) {
        adj_list.resize(number_of_servers);
        visited.assign(number_of_servers, false);

        // Creating adjacency list representation
        // skipping i'th connection
        for(int j = 0; j < connections.size(); j++) {
            if(i == j) continue;

            int u = connections[j][0];
            int v = connections[j][1];
            adj_list[u].push_back(v);
            adj_list[v].push_back(u);
        }

        dfs(0);

        // If all the servers were not reachable from node 0,
        // the i'th connection is a critical connection.
        for(int j = 0; j < number_of_servers; j++) {
            if(visited[j] == false) {
                criticalConnections.push_back(vector{connections[i][0], connections[i][1]});
                break;
            }
        }

        adj_list.clear();
    }

    if(criticalConnections.size() == 0) {
        criticalConnections.push_back(vector{-1, -1});
    }

    return criticalConnections;
}


// -------- END --------
</vector</vector</vector</vector

‍2) optimal_solution.cpp:

The concept of critical connection here is the famous concept in graph theory called  “Bridges”. Question is to find out all the bridges in the given graph.

The idea is to use DFS (Depth First Search). In the DFS tree, any tree edge (u, v) where v is the parent node of u, is a bridge if none of the descendants of u has a back-edge to any of the ancestors of v. This means there is no way from u to v except for the edge (u, v). If a back-edge is found, this means there exists another path from u to v, and node u and v will still be connected if edge(u, v) is removed. Also, the back-edge can’t be a bridge because the edge(u, v) will keep the graph connected if the back-edge is removed.

We maintain an array that stores the discovery times of each vertex computed by DFS. Also, we store the earliest visited vertex (the vertex with minimum discovery time) that can be reached from subtree rooted at v. So we maintain an additional array lowest_time where lowest_time[v] is the minimum of:

1. discovery_time[v]

2. discovery_time[p], for all p for which (v, p) is a back-edge

3. lowest_time[u], for all u for which (v, u) is a tree edge, here u belongs to the subtree of v.

Now, for an edge (u, v), there is a back edge from vertex u or from one of its descendants to v or one of its ancestors if lowest_time[u] <= discovery_time[v]. Thus, if lowest_time[u] > discovery_time[v], edge (u, v) is a bridge.

For better understanding, please have a look at the solution.

Time Complexity:

O(number_of_servers + number_of_connections)

To create adjacency list = O(number_of_connections).

DFS algorithm = O(number_of_servers + number_of_connections).

Auxiliary Space Used:

O(number_of_servers + number_of_connections).

Memory used for adjacency list = O(number_of_servers + number_of_connections).

Memory used for visited, discovery time, lowest time array = O(number_of_servers).

Space Complexity:

O(number_of_servers + number_of_connections).

Memory used for input = O(number_of_connections).

Memory used for output = O(number_of_connections).

Auxiliary space = O(number_of_servers + number_of_connections).

Total space complexity = O(number_of_servers + number_of_connections)

// -------- START --------
vector<vector> adj_list;

// discovery_time[] --> Stores discovery times of visited vertices 
vector discovery_time, lowest_time;
vector visited;
int timer = 0;

// v --> The vertex to be visited
// p --> The parent vertex of v
void dfs(int v, int p, vector<vector> &criticalConnections) {
    visited[v] = true;

    // Set discovery time and initialize lowest time.
    discovery_time[v] = lowest_time[v] = ++timer;
    // Note: discovery time won't change whereas lowest time might be updated.

    // Iterating through adjacent vertices of v.
    for(int u : adj_list[v]){
        // low time should never be updated for edge connecting a node to its parent.
        if(u == p)
            continue;

        // presence of a back edge.
        if(visited[u]) {
            lowest_time[v] = min(lowest_time[v], discovery_time[u]);
        } else {
            dfs(u, v, criticalConnections);

            //check if the edge is a bridge
            if(discovery_time[v] < lowest_time[u])
                criticalConnections.push_back(vector{u, v});

            // Update the lowest_time of v in accordance with the existing back edges
            // from all such descendants which have u on the path from v to itself(the descendant)
            // in the DFS tree.
            lowest_time[v] = min(lowest_time[v], lowest_time[u]);
        }
    }
}

vector<vector> find_critical_connections(int number_of_servers, vector<vector> connections) {
    vector<vector> criticalConnections;

    adj_list.resize(number_of_servers);

    // Creating adjacency list representation
    for(int i = 0; i < connections.size(); i++) {
        int u = connections[i][0];
        int v = connections[i][1];
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    discovery_time.resize(number_of_servers);
    lowest_time.resize(number_of_servers);
    visited.assign(number_of_servers, false);

    // Introducing a hypothetical parent -1 for node 0.
    dfs(0, -1, criticalConnections);

    if(criticalConnections.size() == 0) {
        criticalConnections.push_back(vector{-1, -1});
    }

    return criticalConnections;
}


// -------- END --------