Analyzing Graph Connectiivty Through Node Removal

When removing a node from a graph, we need to calculate the impact on connectivity. Each removal can create multiple connected components, requiring careful tracking of these new components.

Key Concepts

1. Articulation Points: Nodes whose removal increases the number of connected components
2. Component Tracking: For each node u:
   • son_u: Number of child components
   • ans_u: Contribtuion from child components
   • sum_u: Size of subtree rooted at u
   • a_u: Size of component starting at u

Mathematical Formulation

The total impact when removing node i is:

\sum_{tr_i=1}^N S_{tr_i}^2 - S_{tr_i}^2 + \sum_{j=1}^m S_j

Implementation

#include <vector>
#include <algorithm>
using namespace std;

struct SCC {
    vector<vector<int>> graph;
    vector<int> dfn, low, stack;
    vector<bool> in_stack;
    int timestamp = 0;
    
    void tarjan(int u, vector<int>& ans, vector<int>& sum) {
        dfn[u] = low[u] = ++timestamp;
        stack.push_back(u);
        in_stack[u] = true;
        
        int child_sum = 0;
        for (int v : graph[u]) {
            if (!dfn[v]) {
                tarjan(v, ans, sum);
                low[u] = min(low[u], low[v]);
                sum[u] += sum[v];
                
                if (dfn[u] <= low[v]) {
                    ans[u] += sum[v] * sum[v];
                    child_sum += sum[v];
                }
            } else if (in_stack[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        sum[u] += node_weight[u];
        sum[u] = child_sum + node_weight[u];
        
        if (dfn[u] == low[u]) {
            while (true) {
                int v = stack.back();
                stack.pop_back();
                in_stack[v] = false;
                if (u == v) break;
            }
        }
    }
};

Optimization Notes

1. Use Tarjan's algorithm for efifcient SCC detection
2. Track component sizes during DFS traversal
3. Calculate contributions incrementally to avoid recomputation