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

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

If you are at all like me then you might have started wondering whether CP is actually destroying your mental health and causing you to value yourself based on a number on a screen.

But fear not because there are still good reasons to try to make your country's IOI team this year.

Does anyone want to be my friend and go on the slide with me I think that would be fun.

Also perhaps we can go for some healing in the certified medicinal thermal water.

src

Полный текст и комментарии »

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

Автор 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
  • Проголосовать: не нравится