Encontrando Pontes Online

É fornecido um grafo não direcionado. Uma ponte é uma aresta cuja remoção desconecta o grafo (ou, mais precisamente, aumenta o número de componentes conectados). Nossa tarefa é encontrar todas as pontes no grafo fornecido.

Informalmente, o problema é formulado da seguinte maneira: dado um mapa de cidades conectadas com estradas, encontre todas as estradas "importantes", isto é, estradas que, quando removidas, causam o desaparecimento de um caminho entre alguns pares de cidades, ou seja, algumas cidades ficam inacessíveis a outras.

Já existe o artigo "Localizando pontes em um grafo em $O(N+M)$" que resolve esta tarefa com uma DFS. Esse algoritmo será muito mais complicado, mas tem uma grande vantagem: o algoritmo descrito neste artigo funciona on-line, o que significa que o grafo de entrada(input) não precisa ser conhecido antecipadamente. As arestas são adicionadas uma vez por vez e, após cada adição, o algoritmo reconta todas as pontes no grafo atual. Em outras palavras, o algoritmo foi projetado para funcionar eficientemente em um grafo dinâmico, ou seja, com constantes mudanças.

Mais rigorosamente, a declaração do problema é a seguinte: Inicialmente, o grafo está vazio e consiste de $n$ vértices. Em seguida, recebemos pares de vértices $(a, b)$, que indicam uma aresta adicionada ao grafo. Após cada aresta recebida, ou seja, após adicionar cada aresta, imprima o número atual de pontes no grafo.

Também é possível manter uma lista de todas as pontes, bem como dar suporte explícito aos componentes conectados por 2 arestas no grafo.

O algoritmo descrito abaixo funciona em $O(n \log n + m)$, onde $m$ é o número de arestas. O algoritmo é baseado na estrutura de dados "Disjoint Set Union". No entanto, a implementação neste artigo leva $O(n \log n + m \log n)$, porque usa a versão simplificada do DSU sem a "union by rank".

Algoritmo

Primeiro, vamos definir um "componente conectado por $k$ arestas": é um componente conectado que permanece conectado sempre que removemos um número de arestas menor que $k$.

As pontes dividem o grafo em componentes conectados por 2 arestas. Se comprimirmos cada um desses componentes conectados por duas arestas em vértices e apenas deixarmos as pontes como arestas no grafo comprimido, obteremos um grafo acíclico, ou seja, uma floresta.

O algoritmo descrito abaixo mantém essa floresta explícita, bem como os componentes conectados por 2 arestas.

Inicialmente, quando o grafo está vazio, ele contém $n$ componentes conectados por 2 arestas, que por si só não estão conectados.

Ao adicionar a próxima aresta $(a, b)$ podem ocorrer três situações:

Consequentemente, toda a tarefa é reduzida à implementação efetiva de todas essas operações na floresta de componentes conectados por duas arestas.

Estruturas de dados para armazenar a floresta

A única estrutura de dados necessária é o Disjoint Set Union. De fato, faremos duas cópias dessa estrutura: uma será para manter os componentes conectados, a outra para manter os componentes conectados por 2 arestas. Além disso, armazenamos a estrutura das árvores na floresta de componentes conectados por 2 arestas por meio de ponteiros: cada componente conectado por 2 arestas armazenará o índice par[] de seu ancestral na árvore.

Agora, as operações que precisamos aprender a implementar:

Implementação

Aqui está a implementação final de todo o algoritmo.

Como mencionado anteriormente, por uma questão de simplicidade, o DSU dos componentes conectados com 2 arestas é implementado sem union by rank, portanto, a complexidade resultante será $O(\log n)$ em média.

Também nesta implementação, as próprias pontes não são armazenadas, apenas sua contagem: bridges. No entanto, não será difícil criar um set de todas as pontes.

Inicialmente, a chamada da função init(), inicializa as duas DSUs (criando um conjunto separado para cada vértice e definindo o tamanho igual a um) e define os ancestrais par.

A função principal é add_edge(a, b), que processa e adiciona uma nova aresta.

vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;
int bridges;
int lca_iteration;
vector<int> last_visit;

void init(int n) {
    par.resize(n);
    dsu_2ecc.resize(n);
    dsu_cc.resize(n);
    dsu_cc_size.resize(n);
    lca_iteration = 0;
    last_visit.assign(n, 0);
    for (int i=0; i<n; ++i) {
        dsu_2ecc[i] = i;
        dsu_cc[i] = i;
        dsu_cc_size[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}

int find_2ecc(int v) {
    if (v == -1)
        return -1;
    return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);
}

int find_cc(int v) {
    v = find_2ecc(v);
    return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);
}

void make_root(int v) {
    v = find_2ecc(v);
    int root = v;
    int child = -1;
    while (v != -1) {
        int p = find_2ecc(par[v]);
        par[v] = child;
        dsu_cc[v] = root;
        child = v;
        v = p;
    }
    dsu_cc_size[root] = dsu_cc_size[child];
}

void merge_path (int a, int b) {
    ++lca_iteration;
    vector<int> path_a, path_b;
    int lca = -1;
    while (lca == -1) {
        if (a != -1) {
            a = find_2ecc(a);
            path_a.push_back(a);
            if (last_visit[a] == lca_iteration)
                lca = a;
            last_visit[a] = lca_iteration;
            a = par[a];
        }
        if (b != -1) {
            path_b.push_back(b);
            b = find_2ecc(b);
            if (last_visit[b] == lca_iteration)
                lca = b;
            last_visit[b] = lca_iteration;
            b = par[b];
        }

    }

    for (int v : path_a) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
    for (int v : path_b) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
}

void add_edge(int a, int b) {
    a = find_2ecc(a);
    b = find_2ecc(b);
    if (a == b)
        return;

    int ca = find_cc(a);
    int cb = find_cc(b);

    if (ca != cb) {
        ++bridges;
        if (dsu_cc_size[ca] > dsu_cc_size[cb]) {
            swap(a, b);
            swap(ca, cb);
        }
        make_root(a);
        par[a] = dsu_cc[a] = b;
        dsu_cc_size[cb] += dsu_cc_size[a];
    } else {
        merge_path(a, b);
    }
}

O DSU para os componentes conectados por 2 arestas é armazenado no vetor dsu_2ecc, e a função que retorna o representante é find_2ecc(v). Essa função é usada várias vezes no restante do código, pois após a compactação de vários vértices em um deles, todos esses vértices deixam de existir e, em vez disso, apenas o vértice/nó líder do DSU tem o ancestral correto par na floresta de componentes conectados por duas arestas.

O DSU para os componentes conectados é armazenado no vetor dsu_cc, e também há um vetor adicional dsu_cc_size para armazenar os tamanhos dos componentes. A função find_cc(v) retorna o nó líder do componente de conectividade (que na verdade é a raiz da árvore).

O enraizamento de uma árvore make_root(v) funciona como descrito: percorre do vértice $v$ pelos ancestrais até o vértice raiz, redirecionando sempre o ancestral par na direção oposta. O link para o representante do componente conectado dsu_cc também é atualizado, para que aponte para o novo vértice raiz. Após o re-enraizamento, precisamos atribuir à nova raiz o tamanho correto do componente conectado. Também temos que ter cuidado ao chamar find_2ecc() para obter os representantes do componente conectado por 2 arestas, em vez de outros vértices que já foram compactados.

A função de compressão e procura do ciclo merge_path(a, b) também é implementada como descrito acima. Ela procura pelo LCA de $a$ e $b$ "aumentando" esses nós em paralelo, até encontrarmos um vértice pela segunda vez(que já tenha sido marcado). Para fins de eficiência, escolhemos um identificador único para cada chamada para encontrar o LCA, e marcamos os vértices que foram percorridos com ele. Isso funciona em $O(1)$, enquanto outras abordagens, como usar $set$ apresentam desempenho pior. Os caminhos passados ​​são armazenados nos vetores path_a e path_b, e os usamos para percorrê-los uma segunda vez até o LCA, obtendo assim todos os vértices do ciclo. Todos os vértices do ciclo são compactados anexando-os ao LCA; portanto, a complexidade média é de $O(\log n)$ (já que não usamos "union by rank"). Todas as arestas pelas quais passamos são pontes, portanto subtraímos 1 para cada aresta no ciclo.

Finalmente, a função de consulta add_edge(a, b) determina os componentes conectados nos quais os vértices $a$ e $b$ estão. Se eles estiverem em diferentes componentes de conectividade, uma árvore menor será re-enraizada e, em seguida, anexada à árvore maior. Caso contrário, se os vértices $a$ e $b$ estiverem em uma árvore, mas em diferentes componentes conectados por 2 arestas, a função merge_path(a, b) será chamada, o que detectará o ciclo e o compactará em um componente conectado por 2 arestas.