Blog entries - Codeforces

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.

Proof

The bridge tree is connected if the original graph is connected.

Proof

The bridge tree does not contain any cycles.

Proof

The bridge tree will contain $$$\le N$$$ nodes, where $$$N$$$ is the number of nodes in the original graph.

Proof

The bridge tree will contain $$$\le N - 1$$$ edges, where $$$N$$$ is the number of nodes in the original graph.

Proof

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?

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$$$?

aryan12's blog

Definition of Bridges

Pre-Requisites

Introduction

Properties of the bridge tree

Pseudocode for making the bridge tree

The time complexity of making the bridge tree

Sample problem

Solution

Extra Exercise

Other Problems