Источник:



Круги друзей
В классе N учащихся. Некоторые из них друзья, а некоторые нет. Их дружба носит транзитивный характер…leetcode.com



В классе N учеников. Некоторые из них друзья, а некоторые нет. Их дружба носит транзитивный характер. Например, если A является прямым другом B, а B прямым другом C, то A является косвенным другом C. , И мы определили круг друзей, это группа студентов, которые являются прямыми или косвенными друзьями.

Дана матрица N*N M, представляющая дружеские отношения между учащимися в классе. Если M[i][j] = 1, то i-й и j-й ученики являются прямыми друзьями друг друга, иначе нет. И вы должны вывести общее количество кругов друзей среди всех учеников.

Пример 1:

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

Пример 2:

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Примечание.

  1. N находится в диапазоне [1200].
  2. M[i][i] = 1 для всех учащихся.
  3. Если M[i][j] = 1, то M[j][i] = 1.

Мое решение С#/Java находится здесь:

https://github.com/jiajionline/LeetcodeSolutionWithMultipleLanguages/tree/master/Friend%20Circles