Блог пользователя kriepiekrollie

Автор kriepiekrollie, история, 23 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
23 месяца назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

.