547.フレンドサークル-LeetCode

547 Friend Circles Leetcode

There are N students in the class. Some of them are friends and some are not. Their friendship is transitive. If A is known to be a friend of B and B is a friend of C, then we can think of A as a friend of C. The so-called circle of friends refers to the collection of all friends. Given a matrix M of N * N, it represents a friend relationship between students in the class. If M[i][j] = 1, it means that the i-th and j-student are known to be friends, otherwise they do not know. You must output the total number of known circle of friends among all students. Example 1: Enter: [[1,1,0], [1,1,0], [0,0,1]] Output: 2 Note: It is known that student 0 and student 1 are friends with each other and they are in a circle of friends. The second student is in a circle of friends. So return 2. Example 2: Enter: [[1,1,0], [1,1,1], [0,1,1]] Output: 1 Note: It is known that student 0 and student 1 are friends with each other, and student 1 and student 2 are friends with each other, so student 0 and student 2 are also friends, so the three of them are in a circle of friends and return 1. Note: N is in the range of [1,200]. For all students, there is M[i][i] = 1. If M[i][j] = 1, then M[j][i] = 1.

方法 ： DFS （DFSを使用して接続されているすべてのコンポーネントを検索します）

// Time complexity: O(n^2) // Space complexity: O(n) class Solution { public: int findCircleNum(vector& M) { if(M.empty())return 0 int n = M.size() vector visited(n, 0) int ans = 0 for (int i = 0 i & M,int curr,vector& visited,int n){ if(visited[curr])return visited[curr]=1 // visit all friends(neighbors) for (int i = 0 i