A brief introduction of Tarjan and E-DCC（EBC)

Revision en1, by RDFZzzx, 2022-07-26 07:20:16

The algorithm of Tarjan is used to solve some problems which is about the connectedness of the Graph. Today I am going to introduce the key to solving E-DCC by Tarjan.

This problem is the template of E-DCC.

## Defination : What is E-DCC?

The full name of E-DCC is edge double connectivity component.

Some people call it EBC (Edge Biconnected Component).

An E-DCC is a component that you cut any one of the edges, the graph is still connected.

For example, in this graph, nodes in same color are in the same E-DCC, and there are $3$ E-DCCs in this graph. They are:

• node $1$

• node $2$, $3$, $4$, $5$, $6$

• node $7$

## Solution : How to find E-DCC by Tarjan?

### Bridge

First, we should know what BRIDGE is. - A bridge is an edge in the graph, and if you cut the edge off, the graph is not connected.

### Tarjan

Tarjan is one of the algorithms which can solve this problems.

First I am going to introduce two arrays to you:

• $low_x$: An array of trace values representing the minimum idx of points on a search tree rooted at $x$ which can be reached by only one edge which is not in the search tree.

• $dfn_x$: Timestamp array, representing the order it was visited.

For example we can get the two values of the nodes:

#### How to calculate $low_x$?

We assume that there is an undirected edge from the node $x$ to the node $y$. There are two conditions:

• First: If node $y$ is a node of the subtree of node $x$, so low[x] = min(low[x], low[y]);
• Secound: Else low[x] = min(low[x], dfn[y]);

Node that: In the secound condition, it is $dfn_y$, and it isn't $low_y$.

We should look back to the defination:

by only one edge which is not in the search tree

Only one edge!

#### How to find Bridges?

If the undirected edge from x to y is a Bridge, if and only if (necessary and sufficient conditions) $dfn_x \lt low_y$.

Lets look back to the example:

For node $2$, $dfn_2 = 2$ and $low_2 = 7$, so edge (2 -> 7) is a bridge.

Because if the edge was cut, we can not goes back to node $7$ from node 2.

// code of finding bridges
void tarjan(int node, int in_edge)
{
dfn[node] = low[node] = ++id;
for (int i = head[node]; i; i = e[i].nxt)
{
const int to = e[i].to;
if (dfn[to] == 0)
{
tarjan(to, i);
if (dfn[node] < low[to])
b[i] = b[i ^ 1] = 1;
low[node] = min(low[node], low[to]);
}
else if (i != (in_edge ^ 1))
low[node] = min(low[node], dfn[to]);
}
}


### E-DCC

If you know how to find Bridges, it will be easy for you to find all the E-DCC.

Cut all the bridges off, then we can get all the E-DCC.

We can solve the problem like this because in each E-DCC there is no bridges.

// code of finding E-DCC
void dfs(int node, int ndcc)
{
dcc[node] = ndcc;
Ans[ndcc - 1].push_back(node);
for (int i = head[node]; i; i = e[i].nxt)
{
int to = e[i].to;
if (dcc[to] || b[i]) continue;
dfs(to, ndcc);
}
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en1 RDFZzzx 2022-07-26 07:20:16 3556 Initial revision (published)