Descripción del problema

Un administrador de red gestiona un sistema de N computadoras conectadas por M enlaces. La red es conexa: cualquier par de computadoras puede comunicarse directa o indirectamente. Algunos enlaces son críticos (puentes), ya que su falla desconecta partes de la red. El administrador añade nuevos enlaces uno por uno, y se debe reportar cuántos puentes quedan después de cada inserción.

Parámetros: N ≤ 100,000, M ≤ 200,000, consultas Q ≤ 1,000.

Estrategia de resolución

Ejecutar Tarjan para detectar puentes en cada consulta sería demasiado costoso. En su lugar, se aplica un enfoque de tres fases:

1. Detección de puentes: Recorrer el grafo con el algoritmo de Tarjan para identificar todas las aristas puente.
2. Contracción de componentes biconectados por aristas: Colapsar cada componente 2-edge-connected en un único nodo, formando un árbol donde cada arista corresponde a un puente original.
3. Procesamiento de cosnultas con LCA: Al añadir una arista entre u y v, calcular el LCA de sus componentes en el árbol. Todas las aristas en los caminos de u y v hacia su LCA dejan de ser puentes. Llevando un contador de aristas "eliminadas", la respuesta es puentes_totales − eliminadas.

Entrada de ejemplo

3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

Salida de ejemplo

Case 1:
1
0

Case 2:
2
0

Implementación en C++

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
const int MAXM = 400005;

struct Arc {
    int dst, nxt;
} graph[MAXM], tree[MAXM];

int gHead[MAXN], tHead[MAXN];
int gCnt, tCnt;

int disc[MAXN], lowVal[MAXN], timer;
bool bridge[MAXM];
int bridgeTotal;

int component[MAXN];
bool seen[MAXN];

int ancestor[MAXN], level[MAXN];
bool covered[MAXN];
int removedCount;

int n, m;

void addGraphArc(int u, int v) {
    graph[gCnt].dst = v;
    graph[gCnt].nxt = gHead[u];
    gHead[u] = gCnt++;
}

void addTreeArc(int u, int v) {
    tree[tCnt].dst = v;
    tree[tCnt].nxt = tHead[u];
    tHead[u] = tCnt++;
}

void initGraph() {
    gCnt = 0;
    memset(gHead, -1, sizeof(gHead));
}

void initTree() {
    tCnt = 0;
    memset(tHead, -1, sizeof(tHead));
}

// Tarjan: detección de puentes
void tarjanBridge(int u, int fromEdge) {
    disc[u] = lowVal[u] = ++timer;
    for (int i = gHead[u]; i != -1; i = graph[i].nxt) {
        if (i == (fromEdge ^ 1)) continue;
        int v = graph[i].dst;
        if (!disc[v]) {
            tarjanBridge(v, i);
            lowVal[u] = min(lowVal[u], lowVal[v]);
            if (lowVal[v] > disc[u]) {
                bridge[i] = bridge[i ^ 1] = true;
                bridgeTotal++;
            }
        } else {
            lowVal[u] = min(lowVal[u], disc[v]);
        }
    }
}

// Asignar ID de componente recorriendo aristas no puente
void colorComponent(int u, int cid) {
    seen[u] = true;
    component[u] = cid;
    for (int i = gHead[u]; i != -1; i = graph[i].nxt) {
        if (bridge[i]) continue;
        int v = graph[i].dst;
        if (!seen[v]) {
            colorComponent(v, cid);
        }
    }
}

// Construir profundidad y padre en el árbol contraído
void buildTree(int u, int par) {
    for (int i = tHead[u]; i != -1; i = tree[i].nxt) {
        int v = tree[i].dst;
        if (v == par) continue;
        ancestor[v] = u;
        level[v] = level[u] + 1;
        buildTree(v, u);
    }
}

// LCA: marcar aristas del camino como cubiertas
int lcaPath(int u, int v) {
    int cnt = 0;
    while (u != v) {
        if (level[u] > level[v]) {
            if (!covered[u]) {
                covered[u] = true;
                cnt++;
            }
            u = ancestor[u];
        } else {
            if (!covered[v]) {
                covered[v] = true;
                cnt++;
            }
            v = ancestor[v];
        }
    }
    return cnt;
}

int main() {
    int caseNo = 1;
    while (scanf("%d %d", &n, &m) && (n || m)) {
        initGraph();
        memset(disc, 0, sizeof(disc));
        memset(lowVal, 0, sizeof(lowVal));
        memset(bridge, false, sizeof(bridge));
        memset(seen, false, sizeof(seen));
        timer = bridgeTotal = 0;

        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            addGraphArc(a, b);
            addGraphArc(b, a);
        }

        tarjanBridge(1, -1);

        // Contracción: asignar componentes
        int compTotal = 0;
        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                colorComponent(i, ++compTotal);
            }
        }

        // Construir árbol a partir de aristas puente
        initTree();
        memset(ancestor, -1, sizeof(ancestor));
        memset(covered, false, sizeof(covered));
        removedCount = 0;

        for (int u = 1; u <= n; u++) {
            for (int i = gHead[u]; i != -1; i = graph[i].nxt) {
                if (bridge[i] && (i & 1) == 0) {
                    int v = graph[i].dst;
                    addTreeArc(component[u], component[v]);
                    addTreeArc(component[v], component[u]);
                }
            }
        }

        level[1] = 1;
        buildTree(1, -1);

        printf("Case %d:\n", caseNo++);

        int q;
        scanf("%d", &q);
        while (q--) {
            int a, b;
            scanf("%d %d", &a, &b);
            removedCount += lcaPath(component[a], component[b]);
            printf("%d\n", bridgeTotal - removedCount);
        }
        printf("\n");
    }
    return 0;
}

Complejidad

• Tarjan (puentes): O(N + M)
• Contracción: O(N + M)
• Por consulta: O(profundidad del árbol) en el caso peor, amortizado O(1) por arista cubierta
• Total: O(N + M + Q · N) en el peor caso, suficientemente eficiente para los límites dados