Saltar al contenido

Pares que se siguen mutuamente

Fácil#adjacency-set#directed-graph~15 min

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

Tiempo objetivo
O(n + m)
Espacio objetivo
O(n + m)

Restricciones

  • people are numbered 0 to n - 1
  • pairs may repeat
  • nobody follows themselves

¿Lo que te frena es la idea y no el código? Lista vs. matriz lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio