Note

Biconnectivity in graphs is an important concept used to identify biconnected components (BCCs). A graph is biconnected if it is connected and does not have any articulation points, meaning removing any single vertex will not disconnect the graph. The biconnected components of a graph are maximal biconnected subgraphs.

Strict Definition: A BCC should contain at least three vertices in a cycle, ensuring that the removal of any single vertex does not disconnect the component.

In practical implementations:

Computational Interpretation: An edge connecting two vertices (without forming part of a larger cycle) is sometimes considered a trivial BCC for completeness in algorithms. This interpretation is adopted for simplicity and ensures that all edges are included in the identification of BCCs.

BCC vs SCC

The concepts of Biconnected Components (BCCs) and Strongly Connected Components (SCCs) are fundamentally different, and thus the algorithms to find them differ significantly. Both concepts are related to graph theory but apply to different types of graphs and have different implications.

AspectStrongly Connected Components (SCCs)Biconnected Components (BCCs)
Graph TypeDirected GraphsUndirected Graphs
DefinitionA maximal subset of vertices where for every pair ( U ) and ( V ), there is a directed path from ( U ) to ( V ) and from ( V ) to ( U ).A maximal subgraph where the removal of any single vertex does not disconnect the rest of the subgraph. Involves cycles or edges.
Key FocusVertex connectivity considering directionalityEdge connectivity without considering directionality
Typical AlgorithmsKosaraju’s, Tarjan’s, Gabow’s algorithmsTarjan’s algorithm for articulation points and bridges
ApplicationsDetecting cycles, strong relationships in directed networks like web pages, social networksNetwork reliability, circuit design, understanding the resilience of networks to node failure

Code

#include <iostream>
#include <vector>
#include <stack>

std::vector<std::vector<int>> tarjan(int num_vertices, const std::vector<int>& row_ptr, const std::vector<int>& col_idx) {
    std::vector<int> discovery_time(num_vertices, -1), low_time(num_vertices, -1), parent(num_vertices, -1);
    std::vector<bool> visited(num_vertices, false);
    std::stack<int> stack;
    std::vector<std::vector<int>> bcc;
    int time = 0;

    auto dfs = [&](int source, auto&& dfs_ref) -> void {
        discovery_time[source] = low_time[source] = time++;
        visited[source] = true;
        stack.push(source);

        for (int i = row_ptr[source]; i < row_ptr[source + 1]; ++i) {
            int target = col_idx[i];

            if (!visited[target]) {
                parent[target] = source;
                dfs_ref(target, dfs_ref);
                low_time[source] = std::min(low_time[source], low_time[target]);

                if (low_time[target] >= discovery_time[source]) {
                    std::vector<int> component;
                    while (stack.top() != target) {
                        component.push_back(stack.top());
                        stack.pop();
                    }
                    component.push_back(target);
                    stack.pop();
                    component.push_back(source);
                    bcc.push_back(component);
                }
            } else if (target != parent[source]) {
                low_time[source] = std::min(low_time[source], discovery_time[target]);
            }
        }
    };

    for (int i = 0; i < num_vertices; ++i) {
        if (!visited[i]) {
            dfs(i, dfs);
            if (!stack.empty()) {
                std::vector<int> component;
                while (!stack.empty()) {
                    component.push_back(stack.top());
                    stack.pop();
                }
                bcc.push_back(component);
            }
        }
    }
    return bcc;
}

int main() {
    int num_vertices = 6;
    std::vector<int> row_ptr = {0, 2, 4, 7, 10, 12, 14};
    std::vector<int> col_idx = {1, 2, 0, 2, 0, 1, 3, 2, 4, 5, 3, 5, 3, 4};

    auto bccs = tarjan(num_vertices, row_ptr, col_idx);

    // Print the BCCs
    for (const auto& component : bccs) {
        std::cout << "BCC: ";
        for (int v : component) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}