Pular para o conteúdo

Pares que se seguem

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

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

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

Travou na ideia, e não no código? Lista vs. matriz explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado