Pares que se seguem
A missão
Problema
Um app social guarda quem segue quem como uma lista de pares [a, b], em que a pessoa a segue a pessoa b, com as pessoas numeradas de 0 a n - 1. A lista pode conter o mesmo par mais de uma vez, e ninguém segue a si mesmo. Retorne quantos pares não ordenados de pessoas se seguem mutuamente.
Exemplos
Input: n = 4, follows = [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 2]]
Output: 2
Por quê: 0 e 1, e 2 e 3; 1 segue 2, mas não o contrário
Input: n = 3, follows = [[0, 1], [0, 1], [1, 0]]
Output: 1
Por quê: o par repetido ainda descreve um único par mútuo
Input: n = 2, follows = []
Output: 0
Por quê: edge case: ninguém segue ninguém
Dicas
0 / 3
Para cada a que segue b, a pergunta é se b também segue a. Com que rapidez uma representação de grafo consegue responder a isso?
Uma matriz de adjacência responde em tempo constante, mas precisa de n ao quadrado de memória. Um conjunto de vizinhos por pessoa também responde em tempo constante, em média, e só guarda as relações que existem.
Crie, para cada pessoa, um conjunto das pessoas que ela segue, o que também descarta pares repetidos. Depois, para cada pessoa a e cada b no conjunto de a, conte o par quando a for menor que b e a aparecer no conjunto de b.
- Tempo-alvo
- O(n + m)
- Espaço-alvo
- O(n + m)
Restrições
- people are numbered 0 to n - 1
- pairs may repeat
- nobody follows themselves
Solução
Guardar quem cada pessoa segue em um conjunto (set) gera uma lista de adjacência que também serve como teste rápido de aresta, que é a única pergunta que este problema faz o tempo todo. Os conjuntos também absorvem pares repetidos, então uma duplicata nunca é contada duas vezes. Cada par mútuo é visto duas vezes, uma a partir de cada pessoa, e o teste a < b mantém exatamente uma dessas ocorrências. O tempo é O(n + m), em média, para m pares da lista, e o espaço é O(n + m).
def mutual_pairs(n, follows):
adj = [set() for _ in range(n)] # adjacency sets: fast edge tests
for a, b in follows:
adj[a].add(b)
count = 0
for a in range(n):
for b in adj[a]:
if a < b and a in adj[b]: # a < b counts each pair once
count += 1
return count
print(mutual_pairs(4, [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 2]])) # -> 2
print(mutual_pairs(3, [[0, 1], [0, 1], [1, 0]])) # -> 1
print(mutual_pairs(2, [])) # -> 0Travou na ideia, e não no código? Lista vs. matriz explica isso.