İçeriğe geç

Karşılıklı takip çiftleri

Kolay#adjacency-set#directed-graph~15 dk

Görev tanımı

Problem

Bir sosyal uygulama kimin kimi takip ettiğini [a, b] çiftlerinden oluşan bir liste olarak saklıyor; bu, a kişisinin b kişisini takip ettiği anlamına geliyor ve kişiler 0'dan n - 1'e kadar numaralı. Liste aynı çifti birden fazla kez içerebilir ve kimse kendini takip etmez. Birbirini takip eden kaç sırasız kişi çifti olduğunu döndür.

Örnekler

Input:  n = 4, follows = [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 2]]
Output: 2
Neden: 0 ile 1, 2 ile 3; 1, 2'yi takip ediyor ama tersi değil
Input:  n = 3, follows = [[0, 1], [0, 1], [1, 0]]
Output: 1
Neden: tekrar eden çift yine tek bir karşılıklı çifti tarif eder
Input:  n = 2, follows = []
Output: 0
Neden: edge case: kimse kimseyi takip etmiyor

İpuçları

0 / 3

Hedef zaman
O(n + m)
Hedef alan
O(n + m)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? Liste mi, matris mi bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case