kriepiekrollie's blog

By kriepiekrollie, history, 17 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
17 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

.