Problem Link - Critical Intersections
Problem Statement
Siruseri receives a lot of rainfall during the monsoons and this used to ruin its otherwise excellent roads. A few years ago, a wise Collector converted most of the roads of Siruseri to concrete roads to avoid this nuisance.
However, since there are underground cables (telephone, power, fibre optic … ) and pipes which have to cross the roads and these cables and pipes often need fixing, the collector did not concrete any of the intersections (places where roads meet each other). The intersections were left tar covered. Cables and drains were relaid so as to cross roads only under intersections.
However, during the monsoons the intersections do get ruined and this results in a lot of traffic jams on Siruseri roads.
Recently, the Collector learnt of a new technology that uses small concrete blocks to pave the roads. This gives the road the strength of concrete and, further, a few of these blocks can be removed quite easily to excavate parts of the road if necessary. So he decided to use these concrete blocks to pave all the intersections in Siruseri.
Paving an intersection involves stopping all the traffic through that intersection. Now, he was worried that some of these intersections could be critical. A intersection I is critical if there are two other intersections J and K such that any route from J to K must necessarily pass through I. Notice that if I is critical, then stopping all the traffic through it disconnects at least one pair of intersections from each other.
You may assume that the roads of Siruseri are such that if all the intersections are usable then one can get from any intersection to any other intersection. All the roads in Siruseri permit traffic in both directions (there are no one way streets). Politicians in Siruseri love to see their names on roads and so every road segment connecting a pair of intersections has a different name. Thus a road merely connects two intersections and never pass through any other intersections.
Approach
The problem can be visualized as a graph where intersections are nodes and roads are edges. The task is to find “critical points” in this graph
, which, if removed, would split the graph into separate disconnected parts. These critical points are known as articulation points in graph theory.
To solve this, we explore the graph using a technique called Depth First Search (DFS). The key idea is to track how nodes are connected and determine whether a node is essential for keeping others connected. We calculate two main properties for each node:
-
When it was discovered during the traversal.
-
The earliest reachable node from it, including through its descendants.
By comparing these properties, we can check if removing a node would break connections between other parts of the graph. If so, it is marked as critical. For the root node, it is critical only if it connects multiple independent parts of the graph.
Finally, after traversing the graph
, we count and print all such critical intersections, ensuring we handle all nodes and edges efficiently.
Time Complexity
O(V + E), where V is the number of intersections and E is the number of roads.
Space Complexity
O(V + E) for storing the graph and auxiliary arrays.