2-Edge-Connected Components

Revision en2, by kriepiekrollie, 2022-12-11 16:15:32

What is the best implementation of finding 2CCs in a graph and compressing it into a tree?

This is what I currently use:

// include some implementation of dsu data structure

void dfs(int u, int p = -1)
{
    tin[u] = low[u] = ++timer;
    for (int v : g[u])
        if (v != p)
        {
            if (tin[v])
                low[u] = min(low[u], tin[v]);
            else
            {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                
                // if u and v are in the same 2CC
                if (low[v] <= tin[u])
                    unite(u, v);
            }
        }
}

void compress_graph()
{
    for (int u = 0; u < n; u++)
        for (int v : g[u])
            if (find(u) != find(v))
                G[find(u)].push_back(find(v));
}

Here, $$$g$$$ is the original graph's adjacency list and $$$G$$$ is the compressed 2CC-graph's adjacency list.

Tags 2-edge-connectivity, graph theory, tree, disjoint set union

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kriepiekrollie 2022-12-11 16:15:32 67
en1 English kriepiekrollie 2022-12-11 16:14:26 915 Initial revision (published)