Before the tutorial, I would like to thank shiven, socho and animeshf for their valuable comments and for improving the tutorial.
Definition of Bridges
Bridges are those edges in a graph, which upon removal from the graph will make it disconnected.
Pre-Requisites
Finding the bridges in a graph.
Introduction
The idea of a bridge tree is to shrink the maximal components without a bridge into one node, leaving only the bridges of the original graph as the edges in the bridge tree.
In the above image, the bridges of the graph are marked in red. They are the edges between the nodes $$$(3, 4)$$$ and $$$(3, 9)$$$. The maximal components without a bridge are $$$[1, 2, 3]$$$, $$$[4, 5, 6, 7, 8]$$$, $$$[9, 10, 11,12]$$$.
Thus, the bridge tree of the graph will become as follows:
The bridge tree only has $$$3$$$ nodes. The nodes $$$[1, 2, 3]$$$ in the original graph have been shrunk to node $$$1$$$, nodes $$$[4, 5, 6, 7, 8]$$$ have been shrunk to node $$$2$$$, and the nodes $$$[9, 10, 11, 12]$$$ have been shrunk to node $$$3$$$.
Note: Throughout the tutorial, we assume that the given graph is undirected, unweighted and connected.
Properties of the bridge tree
All the bridges of the original graph are represented as edges in the bridge tree.
ProofLet us assume the contrary – there is a bridge that is not represented as an edge in the bridge tree. Let the bridge be between nodes $$$P$$$ and $$$Q$$$ in the initial graph. Under our assumption, there should be a node in the constructed bridge tree which represents the maximal component containing both $$$P$$$ and $$$Q$$$, and hence the bridge $$$P–Q$$$ from the initial graph is present in this component. But by the construction of the bridge tree, only the components without a bridge are shrunk to a single node. Hence, we arrive at a contradiction.
The bridge tree is connected if the original graph is connected.
ProofSince the original graph is connected, the set of bridges must be connecting the set of components without a bridge together. By definition, the set of bridges are the edges, and the set of components without a bridge are nodes. Hence the edges must connect all the nodes. Thus, the bridge tree is connected.
The bridge tree does not contain any cycles.
ProofLet us assume the contrary – the bridge tree contains a cycle. In that case, the edges connecting the nodes in the cycle are not bridges, since removing them does not disconnect the graph. Thus, we can shrink the cycle into a single node. Hence, the bridge tree does not contain any cycles.
The bridge tree will contain $$$\le N$$$ nodes, where $$$N$$$ is the number of nodes in the original graph.
ProofSince we’re only shrinking the components without a bridge, there is no way for the number of nodes to increase. Hence the above statement stands true.
The bridge tree will contain $$$\le N - 1$$$ edges, where $$$N$$$ is the number of nodes in the original graph.
ProofA graph with $$$N$$$ nodes can have $$$\le N - 1$$$ bridges only. Since the edges of the bridge tree are composed of the bridges of the original graph only, the number of edges will also be $$$\le N - 1$$$.
Pseudocode for making the bridge tree
dfs(int node, int component_number) {
component[node] = component_number //All nodes with the same component number will be shrunk into one node in the bridge tree. This is because we aren't traversing a bridge, and thus, "shrinking" the components without a bridge to one node in the bridge tree.
vis[node] = true //so that we don't visit this again.
for every adjacent edge such that the edge is not a bridge {
next = other endpoint of the edge
if vis[next] = true: continue //already visited this node.
dfs(next, component_number);
}
}
main() {
Find all the bridges in the graph //check the pre-requisites section of this blog for this
for i in 1, 2, 3, ..., n and vis[i] = false {
call dfs(i, unique_component_number) //ensure the component number is unique. A simple way to do it is just by incrementing it by 1 whenever you are calling the dfs function.
}
The time complexity of making the bridge tree
In this section, $$$N$$$ stands for the number of nodes and $$$M$$$ stands for the number of edges in the original graph. The bridges in the graph can be found in $$$O(N + M)$$$. The time complexity for the DFS function is $$$O(N + M)$$$. Note that we can store the ID of the edge alongside the adjacent node in the adjacency list. We can have an array isBridge
, and mark isBridge[edge] = true
for every edge which is a bridge. During the DFS, just check if the current edge is marked as a bridge using its stored ID.
Thus the total time complexity will be $$$O((N + M) + (N + M))$$$, which is equivalent to $$$O(N + M)$$$.
Sample problem
We are going to solve this problem.
Let us understand the statement first.
There is a connected, unweighted, undirected graph with $$$N$$$ nodes and $$$M$$$ edges.
According to the statement, for some fixed starting node $$$s$$$ and ending node $$$t$$$, your friend will place a boss in each passage such that it is impossible to travel from $$$s$$$ to $$$t$$$ without using this passage. The word impossible tells us that the bosses can only be placed on bridges.
Why only on bridges?By definition, bridges are edges such that their removal makes the graph disconnected. This means that one needs to traverse through this edge while going from $$$s$$$ to $$$t$$$ if they are on different sides of the bridge. On the contrary, if an edge is not a bridge, then its removal doesn’t make the graph disconnected. This implies that it is still possible to travel from $$$s$$$ to $$$t$$$. Hence, we cannot place a boss on the edges which are not bridges.
Solution
Since we are only concerned regarding the bridges of the graph, we can compress all the maximal components without a bridge into a single node to get the bridge tree of the graph. The bridge tree of the first sample input is depicted below.
You can see that the nodes $$$[1, 2, 3]$$$ in the original graph are shrunk to node $$$1$$$ in the bridge tree. Similarly, node $$$[4]$$$ is shrunk to node $$$2$$$ and node $$$[5]$$$ is shrunk to node $$$3$$$.
This makes the original problem a lot easier. The only thing left is to choose a path from one node in the bridge tree to the other so that the number of edges (bridges in the original graph) along the way is maximum. This can be solved by finding the diameter of a tree.
You can find my solution here.
Extra Exercise
Can you answer queries of the form find the number of bosses we need to place between fixed $$$s$$$ and $$$t$$$?
Other Problems
- 652E, My solution
- 555E, My solution
- 231E
Feel free to suggest any other problems! I'll add them to this section.