É 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".
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:
Ambos os vértices $a$ e $b$ estão no mesmo componente conectado por duas arestas - então essa aresta não é uma ponte e não altera nada na estrutura da floresta, então podemos apenas pular essa aresta. Assim, neste caso, o número de pontes não muda.
Os vértices $a$ e $b$ estão em componentes conectados completamente diferentes, ou seja, cada um faz parte de uma árvore diferente. Nesse caso, a aresta $(a,b)$ se torna uma nova ponte e essas duas árvores são combinadas em uma (e todas as pontes antigas permanecem). Assim, neste caso, o número de pontes aumenta em um.
Os vértices $a$ e $b$ estão em um componente conectado, mas em diferentes componentes conectados por 2 arestas. Nesse caso, essa aresta forma um ciclo junto com algumas das pontes antigas. Todas essas pontes acabam sendo pontes e o ciclo resultante deve ser comprimido em um novo componente conectado por 2 arestas. Assim, neste caso, o número de pontes diminui em dois ou mais.
Consequentemente, toda a tarefa é reduzida à implementação efetiva de todas essas operações na floresta de componentes conectados por duas arestas.
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:
Verifique se os dois vértices estão no mesmo componente conectado / com 2 arestas. É feito com o algoritmo do DSU usual, apenas encontramos e comparamos os representantes das DSUs.
Juntando duas árvores por alguma aresta $(a, b)$. Como pode acontecer que nem o vértice $a$ nem o vértice $b$ sejam as raízes de suas árvores, a única maneira de conectar essas duas árvores é re-enraizar uma delas. Por exemplo, você pode re-enraizar a árvore do vértice $a$ e, em seguida, anexá-la a outra árvore, definindo o ancestral de $a$ para $b$.
No entanto, surge a pergunta sobre a eficácia da operação de re-enraizar:
para re-enraizar a árvore com a raiz $r$ para o vértice $v$, é necessário visitar todos os vértices no caminho entre $v$ e $r$ e redirecionar os ponteiros par[] na direção oposta e também alterar as referências dos ancestrais no DSU responsáveis pelos componentes conectados.
Assim, o custo do enraizamento é $O(h)$, onde $h$ é a altura da árvore. Você pode fazer uma estimativa ainda pior assumindo que o custo é $O(\text{size})$ onde $\text{size}$ é o número de vértices na árvore. A complexidade final não será diferente.
Agora aplicamos uma técnica padrão: re-enraízamos a árvore que contém menos vértices. Então é intuitivamente claro que o pior caso é quando duas árvores de tamanhos aproximadamente iguais são combinadas, o resultado é uma árvore com o dobro do tamanho. Isso não permite que essa situação aconteça várias vezes.
No geral, o custo total pode ser escrito na forma de uma recursão: $$T(n) = \max_{k = 1 \ldots n-1} \left\{ T(k) + T(n - k) + O(\min(k, n - k))\right\}$$ $T(n)$ é o número de operações necessárias para obter uma árvore com $n$ vértices por meio de re-enraizamentos e unificações de árvores. Uma árvore de tamanho $n$ pode ser criada combinando duas árvores menores de tamanho $k$ e $n - k$. Essa recorrência tem a solução $T(n) = O (n \log n)$.
Assim, o tempo total gasto em todas as operações de re-enraizamento será de $O(n \log n)$, se sempre re-enraizarmos a menor das duas árvores.
Teremos que manter o tamanho de cada componente conectado, mas a estrutura de dados DSU torna isso possível sem dificuldade.
Procurando o ciclo formado pela adição de uma nova aresta $(a, b)$. Como $a$ e $b$ já estão conectados na árvore, precisamos encontrar o menor ancestral comum(LCA) dos vértices $a$ e $b$. O ciclo consistirá de caminhos de $b$ para o LCA, do LCA para $b$ e da aresta de $a$ para $b$.
Depois de encontrar o ciclo, comprimimos todos os vértices do ciclo detectado em um vértice. Isso significa que já temos uma complexidade proporcional ao tamanho do ciclo, o que significa que também podemos usar qualquer algoritmo do LCA proporcional ao tamanho e não precisamos usar nenhum mais rápido.
Como todas as informações sobre a estrutura da árvore estão disponíveis na array de ancestrais par[], o único algoritmo LCA razoável é o seguinte:
marque os vértices $a$ e $b$ como visitados, depois vamos para os ancestrais deles, par[a] e par[b], e marcamos eles, e depois avançamos para seus ancestrais e assim por diante, até alcançarmos um vértice já marcado. Esse vértice é o LCA(menor ancestral comum) que estávamos procurando e podemos encontrar os vértices no ciclo percorrendo o caminho de $a$ e $b$ para o LCA novamente.
A complexidade deste algoritmo é proporcional ao tamanho do ciclo desejado.
Compressão do ciclo adicionando uma nova aresta $(a, b)$ em uma árvore.
Precisamos criar um novo componente conectado por 2 arestas, que consistirá em todos os vértices do ciclo detectado (o próprio ciclo detectado poderia consistir em alguns componentes conectados a 2 arestas, mas isso não muda nada). Além disso, é necessário compactá-los de maneira que a estrutura da árvore não seja perturbada, e todos os ponteiros par[] e as duas DSU's ainda estão corretos.
A maneira mais fácil de conseguir isso é comprimir todos os vértices do ciclo para o LCA deles.
De fato, o LCA é o mais alto dos vértices, ou seja, seu ponteiro ancestral par[] permanece inalterado. Para todos os outros vértices do loop, os ancestrais não precisam ser atualizados, pois esses vértices simplesmente deixam de existir. Mas no DSU dos componentes conectados por 2 arestas, todos esses vértices simplesmente apontarão para o LCA.
Implementaremos o DSU dos componentes conectados de 2 arestas sem a otimização do "union by rank"; portanto, obteremos a complexidade $O(\log n)$ em média por consulta. Para atingir a complexidade $O(1)$ em média por consulta, precisamos combinar os vértices do ciclo de acordo com o "union by rank", e então definir par[] de acordo.
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.