Strongly Connected Components
Um grafo direcionado tem n nós, numerados de 0 a n-1, e uma lista de edges, em que [from, to] é uma aresta do nó from para o nó to.
Uma componente fortemente conexa é o maior grupo de nós em que cada nó pode alcançar todos os outros seguindo as arestas. Cada nó pertence a exatamente uma componente, e um nó que não está em nenhum ciclo forma uma componente sozinho. Retorne o número de componentes fortemente conexas.
Função
- ninteger
- o número de nós
- edgesinteger-2d-array
- as arestas direcionadas, cada uma como [from, to]
- Retornainteger
- o número de componentes fortemente conexas
Restrições
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]com0 ≤ from, to < nefrom ≠ to- Nenhuma aresta aparece duas vezes.
Exemplos
- Entrada
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Saída
- 3
- Explicação
- Os nós 0, 1 e 2 formam um ciclo, então alcançam uns aos outros. Os nós 3 e 4 apontam um para o outro. O nó 5 alcança o 4, mas nada volta para o 5, então ele fica isolado: 3 componentes.
- Entrada
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Saída
- 4
- Explicação
- Os nós 0 e 1 apontam um para o outro e formam um componente. A aresta de 2 para 3 vai em apenas uma direção, então 2 e 3 são separados, e o nó 4 não tem nenhuma aresta: 4 componentes.
Para ir além
Quantas arestas seria preciso adicionar para que todo o grafo se tornasse um único componente fortemente conexo?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Dois nós compartilham um componente exatamente quando cada um consegue alcançar o outro. Uma busca a partir de cada nó pode testar isso, mas percorre as mesmas arestas repetidamente. O que uma única busca em profundidade pode revelar sobre onde um componente começa?
Numere os nós na ordem em que uma busca em profundidade os alcança pela primeira vez. Para cada nó, acompanhe também
low: o menor número que ele pode alcançar descendo pela árvore de busca e, em seguida, seguindo uma aresta de volta até um nó cujo componente ainda esteja aberto. Um nó cujolowseja igual ao seu próprio número é o primeiro nó do seu componente.Mantenha os nós visitados em uma pilha. Quando um nó terminar com
lowigual ao seu próprio número, desempilhe até esse nó: esses nós formam um componente, então conte-o. Um dos testes faz a busca chegar a 5000 nós de profundidade, então mantenha sua própria pilha de quadros (nó, próxima aresta) em vez de usar recursão.
Solução
Reduza cada componente a um ponto, e os componentes formarão um grafo sem ciclos. Os algoritmos de Kosaraju e Tarjan usam isso para encontrar todos os componentes em O(n + E), onde E é o número de arestas.
Pesquise para frente e para trás a partir de cada nó
Correta, mas não termina nos maiores testes
Intuição
Os nós u e v compartilham um componente exatamente quando cada um alcança o outro. Portanto, para um nó s que ainda não pertence a nenhum componente, faça uma busca para a frente pelas arestas e uma busca para trás pelas arestas invertidas. Os nós encontrados por ambas as buscas formam seu componente. No primeiro exemplo, a busca para a frente a partir de 0 encontra os nós de 0 a 4, e a busca para trás encontra 0, 1 e 2; portanto, {0, 1, 2} forma um componente.
Cada componente exige duas buscas pela maior parte do grafo. Em uma cadeia de 5000 arestas que passa por 5001 nós, cada nó forma seu próprio componente, e as buscas visitam cerca de 2.5 × 10^7 nós.
Algoritmo
- Construa as listas de arestas de saída e de entrada de cada nó.
- Pegue o próximo nó
ssem componente e conte um novo componente. - Marque o que
salcança pelas arestas de saída e o que o alcança pelas arestas de entrada. - Cada nó marcado por ambas as buscas passa a fazer parte do componente de
s. Quando todos os nós tiverem um, retorne a contagem.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countAlgoritmo de Kosaraju: duas passagens
Intuição
No grafo de componentes, algum componente é um sumidouro, sem arestas saindo dele, e uma busca iniciada dentro dele encontra exatamente esse componente. O algoritmo de Kosaraju ordena as buscas para que cada uma se comporte dessa maneira.
A primeira passagem lista cada nó quando sua busca em profundidade termina. A segunda passagem busca no grafo invertido, que tem os mesmos componentes, começando pelo último nó a terminar. Se uma aresta leva do componente B ao C, o último nó de B termina depois de todos os nós de C. Portanto, quando a segunda passagem chega a C, todos os componentes com uma aresta entrando em C já foram atribuídos, e, no grafo invertido, a busca não pode sair de C.
No primeiro exemplo, os nós terminam na ordem 4, 3, 2, 1, 0, 5. A segunda passagem coleta {5}, depois {0, 1, 2} e, em seguida, {3, 4}.
Algoritmo
- Monte as listas de arestas de saída e de entrada.
- Execute uma busca em profundidade iterativa a partir de cada nó não visitado e acrescente cada nó a
orderquando terminar. - Percorra
ordera partir do final. Para cada nó sem componente, conte um novo componente e faça uma busca a partir dele pelas arestas de entrada, atribuindo cada nó não atribuído que alcançar. Retorne a contagem.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countAlgoritmo de Tarjan: uma passagem com valores low
Intuição
Execute uma busca em profundidade e numere cada nó na ordem em que você o alcança: seu index. Mantenha uma pilha de nós visitados cujo componente ainda está aberto e um valor low: o menor índice que um nó alcança descendo pela árvore de busca e, em seguida, percorrendo uma aresta de volta até um nó nessa pilha.
Quando a busca em um nó termina com low menor que index, algo abaixo dele retorna a um nó aberto anterior, então ele permanece na pilha. Quando são iguais, o nó é o primeiro que a busca visitou em seu componente: desempilhe até chegar a ele e conte um componente. Uma aresta que leva a um nó desempilhado chega a um componente concluído que não pode retornar, então ela é ignorada.
No primeiro exemplo, 3 desempilha {4, 3} e 0 desempilha {2, 1, 0}. A aresta do nó 5 leva ao nó 4, que já foi desempilhado, então 5 é desempilhado sozinho.
Algoritmo
- Para cada nó ainda não visitado, atribua a ele o próximo índice, defina
lowcom o mesmo valor, coloque-o na pilha de nós e coloque o quadro (nó, primeira aresta) na pilha. - Se ainda houver uma aresta no nó do quadro do topo da pilha, siga-a: um destino não visitado recebe um índice e um quadro, e um destino que esteja na pilha de nós reduz
low[node]ao seu índice. - Caso contrário, retire o quadro da pilha e reduza
lowdo nó pai paralow[node]. Selow[node]for igual aindex[node], retire nós da pilha de nós até chegar ao nó e conte um componente.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Armadilhas e casos extremos
- Esquecer nós sem arestas. No segundo exemplo, o nó 4 não aparece em nenhuma aresta e ainda assim é um componente.
- Diminuir
lowpor meio de qualquer nó visitado, em vez de apenas aqueles que estão na pilha. No primeiro exemplo, a aresta5 → 4então impede que 5 feche seu componente. - Tratar as arestas como bidirecionais. Isso conta os componentes conexos: o primeiro exemplo resultaria em 1 em vez de 3.
- Usar recursão em Python. Um ciclo com 5000 nós encadeia 5000 chamadas, cinco vezes o limite padrão de 1000. Mantenha sua própria pilha de quadros.
- Executar a segunda passagem de Kosaraju nas arestas originais ou na ordem em que os nós foram visitados pela primeira vez. Qualquer uma dessas opções mescla componentes que só alcançam uns aos outros em uma direção.
Perguntas frequentes3
Qual é a complexidade de tempo para encontrar componentes fortemente conexos?
Tempo O(n + E) com o algoritmo de Kosaraju ou de Tarjan, pois cada nó e aresta é processado um número constante de vezes. Ambos usam espaço O(n + E) para as listas de arestas e as pilhas de busca.
Você deve usar o algoritmo de Kosaraju ou o de Tarjan?
O algoritmo de Kosaraju consiste em duas buscas simples e é mais difícil de errar. O de Tarjan precisa de uma busca e não exige um grafo invertido, ao custo do controle de low.
Qual é a diferença entre componentes fortemente conexos e componentes conexos?
Componentes conexos ignoram a direção das arestas: dois nós estão conectados quando existe algum caminho entre eles. Componentes fortemente conexos exigem que cada nó consiga alcançar o outro. O primeiro exemplo é um componente conexo, mas contém três componentes fortemente conexos.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def countSCC(n, edges):
# Escreva o código aquiTeste #1
Teste #2
Argumentos
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Saída Esperada
3