Critical Connection
You are given a network with ‘N’ system nodes [0 to N - 1] and ‘M’ connection. Your task is to find out all critical connections in a given network.

Note: A connection between node ‘u’ and ‘v’ is said to be a critical connection, if after removal of a connection ‘u’ - ‘v’, there is no connection between node ‘u’ and ‘v’ and the network goes down.

For example:

For given N = 4, M = 4,

The connection between system node 0 and 1 is a critical connection.

Input Format:

The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test case follow The first line of each test case contains two integers ‘N’ and ‘M’, denoting the number of system nodes and the number of connections. The next ‘M’ line contains two space-separated integers ’u’ and ‘v’, denoting the connection between ‘u’ and ‘v’.

Output Format:

The first line of each test case contains one integer ‘X’, denoting the number of critical connections. The next ‘X’ lines contain two space-separated integers ’u’ and ‘v’, denoting critical connection between ‘u’ and ‘v’and ‘u’ is smaller than ‘v’. The output of each test case will be printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Critical Connection

You are given a network with ‘N’ system nodes [0 to N - 1] and ‘M’ connection. Your task is to find out all critical connections in a given network.

Note: A connection between node ‘u’ and ‘v’ is said to be a critical connection, if after removal of a connection ‘u’ - ‘v’, there is no connection between node ‘u’ and ‘v’ and the network goes down.

For example:

For given N = 4, M = 4,

The connection between system node 0 and 1 is a critical connection.

Input Format:

The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test case follow

The first line of each test case contains two integers ‘N’ and  ‘M’, denoting the number of system nodes and the number of connections.

The next ‘M’ line contains two space-separated integers ’u’ and ‘v’, denoting the connection between ‘u’ and ‘v’.

Output Format:

The first line of each test case contains one integer ‘X’, denoting the number of critical connections.

The next ‘X’ lines contain two space-separated integers ’u’ and ‘v’, denoting critical connection between ‘u’ and ‘v’and ‘u’ is smaller than ‘v’.

The output of each test case will be printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N, M <= 10 ^ 6
0 <= u, v <= N - 1
There are no repeated connections. 

Time Limit: 1 sec.

Accepted Answer

Bridge in a graph

If we observe carefully the critical connection is a similar bridge in a graph(edge whose removal increases the number of components in a graph).

The idea is to do Depth first search(DFS) traversal of the given graph. In DFS tree an edge (‘u’, ‘ v’) (‘u’ is parent of ‘v’ in DFS tree) is bridge if there does not exist any other alternative to reach ‘u’ or an ancestor of ‘u’ from subtree rooted with ‘v’.

In order to implement the above thought, we will maintain two arrays :

low[] : the value low[v] indicates earliest visited vertex reachable from subtree rooted with v.
Disc[]: the value of disc[u] indicates the discovery time of node ‘u’.
The condition for an edge (u, v) to be a bridge is, “low[v] > disc[u]”.

The steps are as follows :

We will use following variables :

timer, to keep track of discovery time.
‘disc’ array, the value of disc[u] indicates the discovery time of node ‘u’.
‘low’ array, the value low[v] indicates earliest visited vertex reachable from subtree rooted with v.
visited array, mark whether node ’i’ is visited or not.
Array of list, to construct graph.

Let ‘criticalConnection(n, ‘connections’)’ be the function that returns all the critical connections in a network, where ‘n’ is the number of nodes in a given network and ‘connections’ contain all connections.

Take a variable ‘timer’, Initialize ‘timer’ to 0.
Take an array ‘disc’ of length ‘n’.
Take an array ‘visited’ of length.
Take an array ‘low’ of length.
Take a variable ‘m’ and initialize it with the size of connections array.
Run a loop from 0 to ‘m’:
- Take a variable ‘u’ and store the first element of connections[i].
- Take a variable ‘v’ and store the second element of connections[i].
- Push ‘u’ in graph[v].
- Push ‘v’ in graph[u].
Take an array ‘ans’ to store the critical connections.
Run a loop from 0 to ‘n’:
- Initialize disc[i] with 0.
- Initialize low[i] with large value.
- Initialize visited[i] with 0.
Make a function dfs(start, ‘ans’, parent, ‘disc’, ‘low’, ‘visited’, ‘graph’, ‘timer’) , to find all the critical connection:
- Run a loop from 0 to ‘n’ - 1
  - If visited[i] is equal to 0
  - Call dfs(start, ‘ans’, parent, ‘disc’, ‘low’, ‘visited’, ‘graph’, ‘timer’) function
- Return ‘ans’ array.

Description of ‘dfs(‘start(s)’, ‘ans’, parent(p),‘disc’, ‘low’, ‘visited’, ‘graph’, ‘timer’)’ function

This utility function finds all the critical connections in a network.

Mark ‘visited[s]’ equal to 1.
Increment the ‘timer’ by 1.
Store the ‘timer’ in ‘disc[s]’ and ‘low[s]’.
Run a loop from 0 to size of graph[s] array ( number of nodes adjacent to the node ‘s’)
- Take a variable ‘adj’ and initialize it with graph[s][i].
- Check if this adjacent node ‘adj’ is visited or not, if visited:
  - Recursively call dfs(‘adj’, ans, ‘s’).
  - Update ‘low[s]’ equal to min of ( low[adj]’ and ‘low[s]’).
  - If ‘low[adj]’ is greater than ‘disc’ of ‘s’, this is a critical connection store in ‘ans’ array.
    - Take a temporary array ‘temp’.
    - Push min of ‘s’ and ‘adj’ in temp.
    - Push max of ‘s’ and ‘adj’ in temp.
- Else if ‘adj’ is not the parent of ‘s’ i.e ‘p’:
  - Update ‘low[s]’ as minimum of ‘low[adj]’ and ‘low[s]’.

Space Complexity: OtherExplanation:

O(M + N), where ‘N’ is the number of nodes and ‘M’ is the number of connections.

Mainly, We are using space in creating a graph, which takes O(N + M) space, visited array, which takes O(N) space, ‘low’ array which takes O(N) space, ‘disc’ array which takes O(N) space. Hence, the overall space complexity is O(N + M) + 3 * O(N) = O(N + M).

Time Complexity: OtherExplanation:

O(M + N), where ‘N’ is the number of nodes and ‘M’ is the number of connections.

We are using the standard ‘dfs’ function that takes O(N + M). Hence, the overall time complexity is O(N + M).

C++ (g++ 5.4)



/*

    Time Complexity : O(M + N)

    Space Complexity: O(M + N)



    Where ‘N’ is the number of nodes and ‘M’ is the number of connections.



*/



// Utility function to find all the critical connections and store it in 'ans' array

void dfs(int s, vector< vector > & ans, int p, int * disc, int * low, bool * visited, vector< vector > &graph, int &timer)

{



    // Mark node 's' visited

    visited[s] = 1;



    // Increament the timer by one

    timer++;



    // Store the discovery time of node 's' in 'disc'

    disc[s] = timer;



    // Initialize the 'low' of 's' with 'timer'

    low[s] = timer;

    

    // Run aloop from 0 to number of nodes adjacent to node 's'

    for(int i = 0; i < graph[s].size(); i++)

    {

        // Store the adjacent of 's' in 'adj' variable

        int adj = graph[s][i];

        

        // If node 'adj' is not visited

        if(visited[adj] == 0)

        {

            

            // Recursively call the function on adjacent 'adj'

            dfs(adj, ans, s, disc, low, visited, graph, timer);

            

            // Update the 'low' of node 's' as the minimum of 'low[adj]' and 'low[s]'

            low[s] = min(low[adj], low[s]);

            

            // If low of adjacent 'adj' is greater than discovery time of parent node 's'

            if(low[adj] > disc[s])

            {

                vector temp;



                temp.push_back(s);

                temp.push_back(adj);

                // Push the critical connection in 'ans'

                ans.push_back(temp);

            }         

                           

        }

        // Else check if current adjacent is not the parent of 's'

        else if(adj != p){



            // Update the low of 's'

            low[s] = min(low[adj], low[s]);

        }

    }



    return ;

}



// Function to find all the critical connection in a network

vector< vector > criticalConnections(int n, vector> & connections) 

{

    

    // Take a variable to track discovery time of each node

     int timer = 0;



    // Array to store the discovery time of each node

    int * disc = new int[n];



    // Array to store the 'low' time of each node

    int * low = new int[n];



    // Array to track whether a node is visited or not

    bool * visited = new bool[n];



    // List to create graph

    vector< vector > graph(n);

    

   

    int m = connections.size();

    

    // Run a loop from 0 to 'm' and create graph by given connections

    for(int i = 0; i < m; i++)

    {

        int u = connections[i][0];

        int v = connections[i][1];

        



        graph[u].push_back(v);

        graph[v].push_back(u);

    }

    

    // Take an array 'ans' to store all the critical connection

    vector< vector > ans;

    

    // Run a loop from 0 to 'n' and initialize 'disc', 'low' and 'visited' array

    for(int i = 0; i < n; i++)

    {

        // Initialy  discovery time of each node is 0.

        disc[i] = 0;



        // Initialy Low of each node is INT_MAX

        low[i] = INT_MAX;



        // Initialy all nodes are unvisited

        visited[i] = false;

    }

    

    // Run a loop from 0 to 'n - 1' , because graph may have more than one component

    for(int i = 0; i < n; i++)

    {

        // If node is not visited

        if(visited[i] == 0)

        {

            

            // Call the helper function with 0 as sthe tarting node and -1 as dummy parent of 's'

            dfs(i, ans, -1, disc, low, visited, graph, timer);



        }

    }

    

    

    

    // Return 'ans'

    return ans;

}

Java (SE 1.8)

/*

    Time Complexity : O(M + N)

    Space Complexity: O(M + N)



    Where 'N' is the number of nodes and 'M' is the number of connections.



*/



import java.util.ArrayList;



public class Solution {

    

    // Utility function to find all the critical connections and store it in 'ans' array

    private static void dfs(int s, ArrayList> ans, int p, ArrayList disc,  ArrayList low,  ArrayList visited, ArrayList> graph, int timer) {



        // Mark node 's' visited

        visited.set(s, 1);



        // Increament the timer by one

        timer++;



        // Store the discovery time of node 's' in 'disc'

        disc.set(s, timer);



        // Initialize the 'low' of 's' with 'timer'

        low.set(s, timer);



        // Run aloop from 0 to number of nodes adjacent to node 's'

        for (int i = 0; i < graph.get(s).size(); i++) {



            // Store the adjacent of 's' in 'adj' variable

            int adj = graph.get(s).get(i);



            // If node 'adj' is not visited

            if (visited.get(adj) == 0) {



                // Recursively call the function on adjacent 'adj'

                dfs(adj, ans, s, disc, low, visited, graph, timer);



                // Update the 'low' of node 's' as the minimum of 'low[adj]' and 'low[s]'

                low.set(s, Math.min(low.get(adj), low.get(s)));



                // If low of adjacent 'adj' is greater than discovery time of parent node 's'

                if (low.get(adj) > disc.get(s)) {

                    

                    ArrayList temp = new ArrayList();



                    temp.add(s);

                    temp.add(adj);

                    

                    // Push the critical connection in 'ans'

                    ans.add(temp);

                }



            }

            

            // Else check if current adjacent is not the parent of 's'

            else if (adj != p) {



                // Update the low of 's'

                low.set(s, Math.min(low.get(adj), low.get(s)));

            }

        }



        return ;

    }





    public static ArrayList> criticalConnections(int n, ArrayList> connections) {

        

        // Take a variable to track discovery time of each node

        int timer = 0;



        // Array to store the discovery time of each node

        ArrayList disc = new ArrayList(n);



        // Array to store the 'low' time of each node

        ArrayList low = new ArrayList(n);



        // Array to track whether a node is visited or not

        ArrayList visited = new ArrayList(n);



        // List to create graph

        ArrayList> graph = new ArrayList>(n);

        

        for (int i = 0; i < n; i++) {

            graph.add( new ArrayList());

        }



        int m = connections.size();



        // Run a loop from 0 to 'm' and create graph by given connections

        for (int i = 0; i < m; i++) {

            int u = connections.get(i).get(0);

            int v = connections.get(i).get(1);



            graph.get(u).add(v);

            graph.get(v).add(u);

        }



        // Take an array 'ans' to store all the critical connection

        ArrayList> ans = new ArrayList>();



        // Run a loop from 0 to 'n' and initialize 'disc', 'low' and 'visited' array

        for (int i = 0; i < n; i++) {

            

            // Initialy  discovery time of each node is 0.

            disc.add(0);



            // Initialy Low of each node is INT_MAX

            low.add(Integer.MAX_VALUE);



            // Initialy all nodes are unvisited

            visited.add(0);

        }



        // Run a loop from 0 to 'n - 1' , because graph may have more than one component

        for (int i = 0; i < n; i++) {



            // If node is not visited

            if (visited.get(i) == 0) {



                // Call the helper function with 0 as sthe tarting node and -1 as dummy parent of 's'

                dfs(i, ans, -1, disc, low, visited, graph, timer);



            }

        }



        // Return 'ans'

        return ans;

    }

}

Python (3.5)

'''

    Time Complexity : O(M + N)

    Space Complexity: O(M + N)



    Where ‘N’ is the number of nodes and ‘M’ is the number of connections.

'''



import sys



# Utility function to find all the critical connections and store it in 'ans' array

def dfs( s, ans, p, disc, low, visited, graph, timer):



    # Mark node 's' visited

    visited[s] = 1



    # Increament the timer by one

    timer += 1



    # Store the discovery time of node 's' in 'disc'

    disc[s] = timer



    # Initialize the 'low' of 's' with 'timer'

    low[s] = timer



    # Run aloop from 0 to number of nodes adjacent to node 's'

    for i in range(len(graph[s])):

        # Store the adjacent of 's' in 'adj' variable

        adj = graph[s][i]



        # If node 'adj' is not visited

        if visited[adj] == 0:



            # Recursively call the function on adjacent 'adj'

            dfs(adj, ans, s, disc, low, visited, graph, timer)



            # Update the 'low' of node 's' as the minimum of 'low[adj]' and 'low[s]'

            low[s] = min(low[adj], low[s])



            # If low of adjacent 'adj' is greater than discovery time of parent node 's'

            if low[adj] > disc[s]:

                temp = []



                temp.append(s)

                temp.append(adj)

                # Push the critical connection in 'ans'

                ans.append(temp)





        # Else check if current adjacent is not the parent of 's'

        elif adj != p:



            # Update the low of 's'

            low[s] = min(low[adj], low[s])



    return





def criticalConnections(n, connections):



    # Take a variable to track discovery time of each node

    timer = 0



    # Array to store the discovery time of each node

    #  Initialy  discovery time of each node is 0.

    disc = [0 for i in range(n)]



    # Array to store the 'low' time of each node

    # Initialy Low of each node is INT_MAX

    low = [sys.maxsize for i in range(n)]



    # Array to track whether a node is visited or not

    # Initialy all nodes are unvisited

    visited = [0 for i in range(n)]



    # List to create graph

    graph =[[] for i in range(n)]







    m = len(connections)



    # Run a loop from 0 to 'm' and create graph by given connections

    for i in range(m):



        u = connections[i][0]

        v = connections[i][1]



        graph[u].append(v)

        graph[v].append(u)



    # Take an array 'ans' to store all the critical connection

    ans = []



    # Run a loop from 0 to 'n - 1' , because graph may have more than one component

    for i in range(n):



        # If node is not visited

        if visited[i] == 0:



            # Call the helper function with 0 as sthe tarting node and -1 as dummy parent of 's'

            dfs(i, ans, -1, disc, low, visited, graph, timer)



    # Return 'ans'

    return ans