One Line Linear Algebraic Solution
The problem is equivalent to finding the number of connected components of the matrix M (with n rows/cols).  Let D be the degree matrix aka the rowsums of M, an
The problem is equivalent to finding the number of connected components of the matrix M (with n rows/cols).  Let D be the degree matrix aka the rowsums of M, and the laplacian matrix be L = D - M. Then the number of connected components of M is given by the dimension of the nullspace of L.  By rank-nullity, this is equal to n - rank(L). This algorithm is GPU-friendly and admits efficient approximations. \n \n```\nimport numpy as np\n\nclass Solution:\n    def findCircleNum(self, M: List[List[int]]) -> int:\n        return len(M) - np.linalg.matrix_rank(np.diag(np.sum(M, axis=1)) - np.array(M))\n```\n\n
['Python', 'Python3']