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);
    }
}