Pares que se siguen mutuamente
La misión
Problema
Una app social guarda quién sigue a quién como una lista de pares [a, b], que significa que la persona a sigue a la persona b, con las personas numeradas de 0 a n - 1. La lista puede contener el mismo par más de una vez, y nadie se sigue a sí mismo. Devuelve cuántos pares no ordenados de personas se siguen mutuamente.
Ejemplos
Input: n = 4, follows = [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 2]]
Output: 2
Por qué: 0 y 1, y 2 y 3; 1 sigue a 2, pero no al revés
Input: n = 3, follows = [[0, 1], [0, 1], [1, 0]]
Output: 1
Por qué: el par repetido sigue describiendo un solo par mutuo
Input: n = 2, follows = []
Output: 0
Por qué: caso límite: nadie sigue a nadie
Pistas
0 / 3
Por cada vez que a sigue a b, la pregunta es si existe el seguimiento inverso, de b a a. ¿Qué tan rápido puede responder eso una representación del grafo?
Una matriz de adyacencia lo responde en tiempo constante, pero necesita memoria de n al cuadrado. Un conjunto de vecinos por persona también lo responde en tiempo constante en promedio y solo guarda los seguimientos que existen.
Construye un conjunto de personas seguidas para cada persona, lo que además descarta los pares repetidos. Luego, para cada persona a y cada b del conjunto de a, cuenta el par cuando a es menor que b y a aparece en el conjunto de b.
- Tiempo objetivo
- O(n + m)
- Espacio objetivo
- O(n + m)
Restricciones
- people are numbered 0 to n - 1
- pairs may repeat
- nobody follows themselves
Solución
Guardar los seguimientos de cada persona como un conjunto da una lista de adyacencia que también sirve como prueba rápida de aristas, que es la única pregunta que este problema hace una y otra vez. Los conjuntos también absorben los pares repetidos, así que un duplicado nunca se puede contar dos veces. Cada par mutuo se ve dos veces, una desde cada persona del par, y la prueba a < b conserva exactamente una de esas apariciones. El tiempo es O(n + m) en promedio para m pares de seguimiento, y el espacio es 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, [])) # -> 0¿Lo que te frena es la idea y no el código? Lista vs. matriz lo explica.