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

Help — biconnected components
Автор Mythic07, история, 6 месяцев назад, По-английски

In a recent Online assessment, i got this beautiful problem.

We are given a connected undirected graph. We have to find the number of triplets i, j and k (i != j != k) such that: on removing vertex j from the graph, vertex i and k becomes unreachable from each other.

1 <= n <= 1e5 (vertices) 1 <= m <= 1e5 (edgee)

We're supposed to utilize the concept of articulation points and 2-vertex-connected components. But couldn't deduce any proper solution.

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

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

Any j that disconnects things must be an articulation point (by definition of articulation point). Given an articulation point j, then i and k must be on "different sides" of j.

A way to formalize this idea of "different sides" could be using biconnected components and the block-cut tree. But I think this is overkill.

For any i and k that are in "the same side" of j, they will be in the same subtree of j in the DFS tree (or in none, if the path to both involves moving to the parent of j).

Therefore, for each articulation point j we want to count all pairs of nodes (i,k) that are across it. I'd use DP over the DFS tree. The simplest formula in my opinion would be to count all pairs of nodes and then remove the ones that don't cross over j.

# g is an adjacency list that only contains directed forward-edges
def compute(u):

    ans = 0
    for v in g[u]:
        ans += compute(v)

    if is_articulation[u]:

        # initially say all pairs of nodes cross u
        ans += choose(n-1, 2)

        # remove pairs within "upwards subtree"
        ans -= choose(n - subtree_size[u], 2)

        for v in g[u]:

            # remove pairs within each child subtree
            ans -= choose(subtree_size[v], 2)

    return ans
→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did the exact same thing. But if fails on the following graph.

    6 and 5 will always lie in 2 different branches of the tree, but they have to be in the same. (or maybe I'm wrong about the decomposition, if so can you please mention some resource?, I've encountered this type of problem, a number of times)

    → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      You are absolutely right. A DFS tree rooted from node 4 will end up with 6 and 5 on different sides of 7. Alright, it's a bit more annoying then.

      The problem is that an articulation point can have multiple children that are in the same biconnected component. So let's condense every biconnected component into a single node, while keeping articulation points intact. This is known as the block-cut tree of a graph.

      Now the problem is gone, so the previous solution works with a little adjustment.

      The only difference is that instead of using literal subtree sizes, we use the sizes in the original graph (each biconnected component adds size equal to its number of non-articulation-point elements)

      # g is the adjacency list of a rooting of the block-cut tree (only forward edges)
ans = 0
for u in articulation_points:
  ans += choose(n - 1, 2)               # all pairs
  ans -= choose(n - subtree_size[u], 2) # remove pairs "above" u
  for v in g:
    ans -= choose(subtree_size[v], 2)   # remove pairs "below" u
      → Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I was thinking that you get all the cycles and their lengths, and then do for each cycle length add this to the running sum: n-CycleLength

I'm not sure if this is correct, but it's the first thing that comes to my mind.

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    didn't get your point. What's the use of cycle lengths?? And, anyways finding all cycles is i guess NP

    → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It seems like it is O(n) to find cycle lengths. My idea was anything that isn't in the same cycle, then there is a way to split them.

      Now that I think about it, it might not work. I forgot a case.

      → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

this question exactly matches with this: CSES problem

→ Ответить