Dynamic Graph Connectivity

When adding a new edge between two nodes in a graph, all bridge edges along the path between those nodes become non-bridge edges. This observation leads to efficient updates using tree decomposition techniques or more straightforward approaches like edge contraction. The following implementation uses Heavy-Light Decomposition combined with a segment tree to efficiently manage dynamic updates and queries related to bridge edges. ### Implementation

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 2e5 + 5;

struct SegmentTree {
    struct Node {
        int left, right, count;
        bool clear;
    } nodes[MAXN * 4];

    void build(int node, int l, int r, int *values) {
        nodes[node].left = l;
        nodes[node].right = r;
        nodes[node].count = 0;
        nodes[node].clear = false;
        if (l == r) {
            nodes[node].count = values[l];
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, values);
        build(node * 2 + 1, mid + 1, r, values);
        nodes[node].count = nodes[node * 2].count + nodes[node * 2 + 1].count;
    }

    void clear_range(int node, int l, int r) {
        if (nodes[node].left >= l && nodes[node].right <= r) {
            nodes[node].count = 0;
            nodes[node].clear = true;
            return;
        }
        push_down(node);
        int mid = (nodes[node].left + nodes[node].right) / 2;
        if (l <= mid) clear_range(node * 2, l, r);
        if (r > mid) clear_range(node * 2 + 1, l, r);
        nodes[node].count = nodes[node * 2].count + nodes[node * 2 + 1].count;
    }

    int query(int node, int l, int r) {
        if (nodes[node].left >= l && nodes[node].right <= r)
            return nodes[node].count;
        push_down(node);
        int mid = (nodes[node].left + nodes[node].right) / 2;
        int result = 0;
        if (l <= mid) result += query(node * 2, l, r);
        if (r > mid) result += query(node * 2 + 1, l, r);
        return result;
    }

    void push_down(int node) {
        if (nodes[node].clear) {
            nodes[node * 2].count = 0;
            nodes[node * 2].clear = true;
            nodes[node * 2 + 1].count = 0;
            nodes[node * 2 + 1].clear = true;
            nodes[node].clear = false;
        }
    }
};

int n, m, head[MAXN], depth[MAXN], parent[MAXN], size[MAXN];
int dfn_order[MAXN], top_chain[MAXN], heavy_child[MAXN];
int edge_count, node_count, edge_values[MAXN], total_bridges;

struct Edge {
    int to, rev;
};

vector<Edge> adj[MAXN];

void add_edge(int u, int v) {
    adj[u].push_back({v, (int)adj[v].size()});
    adj[v].push_back({u, (int)adj[u].size() - 1});
}

void dfs1(int u, int p) {
    size[u] = 1;
    for (auto &e : adj[u]) {
        int v = e.to;
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        parent[v] = u;
        dfs1(v, u);
        size[u] += size[v];
        if (size[v] > size[heavy_child[u]])
            heavy_child[u] = v;
    }
}

void dfs2(int u, int top_node) {
    dfn_order[u] = ++node_count;
    top_chain[u] = top_node;
    if (heavy_child[u])
        dfs2(heavy_child[u], top_node);
    for (auto &e : adj[u]) {
        int v = e.to;
        if (v == parent[u] || v == heavy_child[u]) continue;
        dfs2(v, v);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(u, v);
    }

    depth[1] = 1;
    dfs1(1, -1);
    dfs2(1, 1);

    // Edge processing and segment tree initialization
    // Additional logic for handling queries
    return 0;
}

Falling Sand - Simplified Version

In this problem, we model the sand grains and their dependencies as a directed graph. After constructing the graph, we perform strongly connected components (SCC) decomposition to identify individual blocks. Once the SCCs are identified, we analyze the resulting DAG to count the number of components with zero in-degree, which represents independent sand blocks. ### Implementation

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 4e5 + 5;
int n, m, component_id, timer;
int head[MAXN], dfn[MAXN], low[MAXN], st[MAXN], top;
int component_count, in_degree[MAXN], result;
bool in_stack[MAXN];

vector<int> adj[MAXN], components[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st[++top] = u;
    in_stack[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++component_count;
        do {
            int v = st[top--];
            in_stack[v] = false;
            components[component_count].push_back(v);
        } while (st[top + 1] != u);
    }
}

int main() {
    scanf("%d %d", &n, &m);

    // Grid processing and graph construction

    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan(i);
    }

    // Build DAG of components and calculate in-degrees

    for (int i = 1; i <= component_count; ++i) {
        if (in_degree[i] == 0) ++result;
    }

    printf("%d\n", result);
    return 0;
}