This document explores the concept of biconnected components (BCCs) and their representation using a specialized graph structure called a biconnected components graph, often referred to as a "circle-square tree" or "block-cut tree."

Construction

Similar to vertex-connectivity decomposition (v-dcc), the biconnected components graph transforms a general graph into a tree or a forest. In this graph structure: - Each original vertex corresponds to a "circle node."

• Each biconnected component corresponds to a "square node."

The total number of nodes in a biconnected components graph is \(|V| + c\), where \(|V|\) is the number of original vertices and \(c\) is the number of biconnected components. The construction process involves connecting each square node (representing a BCC) to all the circle nodes (original vertices) that belong to that BCC. This forms a collection of star-like structures (flowers) centered at the square nodes. These structures are then interconnected through the articulation points (cut vertices) of the original graph. Since the number of articulation points is less than \(|V|\), the biconnected components graph has fewer than \(2|V|\) nodes. If the original graph has \(k\) connected components, the resulting biconnected components graph will be a forest of \(k\) trees. Algorithm and Observations

The algorithm for constructing a biconnected components graph is a variation of Tarjan's algorithm for finding articulation points and bridges. It involves a Depth First Search (DFS) traversal of the graph, computing two key arrays: - \(dfn[u]\): The DFS discovery time (order) of vertex \(u\).

• \(low[u]\): The lowest \(dfn\) reachable from vertex \(u\) (including \(u\) itself) by traversing at most one back-edge in the DFS tree, or by following tree edges up to the parent.

The definition of \(low[u]\) allows upward traversal via the parent edge, which is consistent with standard Tarjan's algorithm implementations. Key observations regarding BCCs and the DFS tree are: - Each BCC forms a connected subtree within the DFS tree and contains at least two vertices. A BCC rooted at the shallowest vertex \(u\) in the DFS tree will have \(u\) as its highest point.

• Every tree edge in the DFS tree belongs to exactly one BCC.

Consider a BCC whose highest vertex in the DFS tree is \(u\). The subtree rooted at \(u\) encompasses the entire BCC. If \(v\) is a child of \(u\) and both are in the same BCC, there's a tree edge \(u \to v\). In this scenario, \(low[v]\) will be equal to \(dfn[u]\). Specifically, for a tree edge \(u \to v\), \(u\) and \(v\) belong to the same BCC, and \(u\) is the shallowest vertex in that BCC if and only if \(low[v] = dfn[u]\). The set of vertices belonging to a BCC can be identified using a stack, similar to Tarjan's algorithm. When a BCC is found (i.e., \(low[v] = dfn[u]\) for an edge \(u \to v\)), vertices are popped from the stack untill \(v\) is reached. These popped vertices, along with \(v\), form the BCC. The new square node representing this BCC is then connected to \(u\) and all popped vertices. The provided C++ code implements this Tarjan-based approach to construct the biconnected components graph. It handles graphs with multiple connected components by iterating through all vertices and starting DFS if a vertex hasn't been visited. ```

#include <vector>
#include <algorithm>

const int N = 100010;
std::vector<int> adj[N], bcc_adj[N << 1];
int dfn[N], low[N], timer;
int node_stack[N], top;
int bcc_count;

void find_bccs(int u, int parent) {
    low[u] = dfn[u] = ++timer;
    node_stack[++top] = u;

    for (int v : adj[u]) {
        if (v == parent) continue;
        if (!dfn[v]) {
            find_bccs(v, u);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u]) { // Found a BCC
                bcc_count++;
                int current_bcc_node = N + bcc_count; // Square node
                int popped_node;
                do {
                    popped_node = node_stack[top--];
                    bcc_adj[current_bcc_node].push_back(popped_node);
                    bcc_adj[popped_node].push_back(current_bcc_node);
                } while (popped_node != v);
                bcc_adj[current_bcc_node].push_back(u);
                bcc_adj[u].push_back(current_bcc_node);
            }
        } else {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
}

// Example main function structure (simplified)
int main() {
    int n, m;
    // Read n, m, and graph edges
    // Initialize structures
    // ...

    bcc_count = n; // Initial count of circle nodes
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            find_bccs(i, 0);
            top--; // Adjust stack for disconnected components
        }
    }

    // The bcc_adj now represents the biconnected components graph.
    // Nodes 1 to n are original vertices (circle nodes).
    // Nodes n+1 to n+bcc_count are BCCs (square nodes).

    return 0;
}

A derived conclusion is that for a path between two circle nodes in the biconnected components graph, the set of circle nodes adjacent to the square nodes on that path corresponds to the set of nodes on a simple path in the original graph.

To count the triplets, we can fix (s) and (f). The number of valid (c) is the number of nodes on a simple path between (s) and (f) minus 2. Counting this efficiently involves working with the biconnected components graph. A common technique is to assign weights: assign (-1) to circle nodes and the size of the corresponding BCC to square nodes. The sum of weights along a path between two circle nodes in the biconnected components graph then equals (number of simple paths between (s, f) in original graph) - 2. The problem then transforms into summing (weight \times count_of_paths_passing_through) for all nodes, solvable with tree DP.

The provided C++ code snippet demonstrates how to build the biconnected components graph and calculate the desired count using a DFS-based approach for path counting.

• Point value updates.
• Query for the minimum value on any simple path between two points.

Assigning the minimum of its adjacent circle nodes' values to each square node transforms the problem into finding the minimum on a path in a tree. Point updates on circle nodes require updating all adjacent square nodes, which can be up to \(O(N)\) updates. However, by setting a square node's value to the minimum of its children circle nodes' values, an update to a circle node only needs to propagate to its parent square node. Each square node can maintain its children's values using a multiset. If the Lowest Common Ancestor (LCA) of two query points is a square node, we also need to consider the value of the parent circle node of that square node. ### P4334 [COI2007] Policija

This problem involves queries about connectivity in an undirected graph after removing either edges (bridges) or vertices (articulation points). - Part 2 (Articulation Points): After constructing the biconnected components graph, determining connectivity after removing articulation points is equivalent to checking if two nodes lie on the same path between two specific circle nodes in the biconnected components graph. This can be efficiently handled using LCA on the tree structure (either through binary lifting or heavy-light decomposition).

• Part 1 (Bridges): If two nodes are separated by a bridge, they must be adjacent to the same square node in the biconnected components graph. This reduces the problem to a variant of Part 2, where we consider the biconnected components graph constructed after identifying bridges.

The provided C++ code for this problem constructs the biconnected components graph, identifies bridges, and uses heavy-light decomposition for LCA queries to answer the connectivity questions. ### [ABC318G] Typical Path Problem

Given a simple connected undirected graph, determine if there exists a simple path from \(A\) to \(C\) that passes through \(B\) (\(A \neq B \neq C\)). This condition is met if a path from \(A\) to \(B\) exists that does not pass through \(C\), and a path from \(B\) to \(C\) exists that does not pass through \(A\). The biconnected components graph offers a solution. We can perform a DFS starting from \(A\). When traversing, if we encounter a square node, we increment a counter for its adjacent circle nodes. If we reach \(C\) and the counter for \(B\) is non-zero, it indicates that a path from \(A\) to \(B\) not passing through \(C\) exists, and since \(B\) is on the path to \(C\), the condition is satisfeid. The counter is decremented when backtracking from a square node. The provided C++ solution implements this DFS-based approach on the biconnected components graph.