Help — biconnected components

Revision en1, by Mythic07, 2024-05-24 19:06:22

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.

Tags dfs and similar, implementations, tree, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Mythic07 2024-05-24 19:06:22 495 Initial revision (published)