City And Bridges

The idea is to find the articulation nodes in the graph. The articulation node is the node if removing it along with the edges will disconnect the graph.

For eg. 

In the above figure, nodes with values 2 and 3 are Articulation nodes. As removing them along with edges will disconnect the graph.

After removing the node with value 2, the graph will look like

After removing the node with value 3, the graph will look like

The idea is to use DFS (Depth First Search). In DFS, we follow vertices in tree form called DFS tree. In the DFS tree, a vertex ‘u’ is the parent of another vertex ‘v’, if ‘v’ is discovered by ‘u’. In a DFS tree, a vertex ‘u’ is an articulation point if one of the following two conditions is true. 

1) ‘u’ is the root of the DFS tree and it has at least two children. 

2) ‘u’ is not the root of the DFS tree and it has a child ‘v’ such that no vertex in the subtree rooted with ‘v’ has a back edge to one of the ancestors (in DFS tree) of ‘u’.

We do a DFS traversal of a given graph to find out Articulation Points. In DFS traversal, we maintain a parent[] array where parent[u] stores the parent of the vertex ‘u’. For every vertex, count children. If the currently visited vertex ‘u’ is root (parent[u] is -1) and has more than two children, then store it in an unordered_set. 

For the second case. We maintain an array discovery[] to store the discovery time of vertices. For every node ‘u’, we need to find out the earliest visited vertex (the vertex with minimum discovery time) that can be reached from the subtree rooted with ‘u’. So we maintain an additional array low[] for that.

Approach :

• First make a recursive function, say ‘articulation()’ to find articulation points using DFS taking ‘arr’, current node, say ‘u’ and parent, say ‘par’ as arguments.
• Initialize variable ‘time’  to 0 globally.
• Initialize count of children in variable ‘children’ with 0.
• Mark the current node as visited.
• Intitialise ‘discovery[]’ and ‘low[]’ as discovery[u] = time, low[u] = time and increase time.
• Make an iteration to traverse the adjacency list for ‘u’ vertex.
  • Store the adjacent node of ‘u’ in a variable, say ‘adjacent’
  • If ‘adjacent’ vertex is not visited then:
  • Increment the variable ‘children’ with a value of 1.
  • Store ‘u’ in par[adjacent].
  • Call the function ‘articulation()’ recursively making ‘adjacent’ as ‘u’, as an argument for the DFS traversal.
  • Check if the subtree rooted with ‘adjacent’ has any connection to ancestors of ‘u’
  • low[u] = min(low[u], low[adjacent])
  • For condition 1 of articulation - Check if the parent of ‘u’ is -1 i.e. root of the graph and has more than 1 children then insert the value of ‘u’ in unordered_set ‘art’.
  • For condition 2 of articulation - Check if ‘u’ is not the parent node and the low value of one of its children is more than the discovery value of ‘u’ then insert the value of ‘u’ in unordered_set ‘art’.
• Else, update the low value of ‘u’ for parent function calls.
  • Low[u] = min(low[u], discovery[adjacent]).
• In the given function, First, initialize an array ‘ans’ in which our required answer gets stored.
• iterate throughout the ‘query’ array with the help of iterator pointer ‘i’.
  • If query[i] is present in the set ‘art’ then make the value ans[i] as true.
  • Else make the value ans[i] as false.
• Return the ‘ans’ array to the given function.

O(N + M), where ‘N’ is the number of cities and ‘M’ is the number of bridges in the graph.

As we are simply implementing Depth First Search for the above algorithm which takes O(N + M) time complexity for adjacency list representation.

O(N), where ‘N’ is the number of cities in the graph.

As we are taking an auxiliary space to store the count of discovery time and low time of size = number of vertices. Therefore overall space complexity will be O(N).