LeetCode0547.朋友圈朋友圈【中】【Python】【DFS】问题LeetCode一班有N个学生。他们中有些是朋友，有些则不是。他们的友谊本质上是传递性的。比如A是B的直接朋友，B是C的直接朋友，那么A就是C的间接朋友。而我们定义朋友圈就是一群直接或间接朋友的同学。给定aN*N矩阵M表示班级学生之间的好友关系。如果Mi=1，则第i个和第j个学生彼此是直接朋友，否则不是。并且你要输出所有学生朋友圈的总数。例子1：输入：[[1,1,0],[1,1,0],[0,0,1]]输出：2解释：0号和1号同学是直系好友，所以在朋友圈。2号同学本人在朋友圈。所以返回2。示例2：输入：[[1,1,0],[1,1,1],[0,1,1]]输出：1解释：0号和1号同学是直接朋友，1号和2号同学是直接朋友，所以0号和2号同学是间接朋友。都在同一个朋友圈，所以返回1。注意：N在[1,200]范围内。所有学生Mi=1。如果Mi=1，则Mj=1。班级有N个学生，一些其中有些是朋友，有些则不是。他们的友谊是可以传递的。如果知道A是B的朋友，B是C的朋友，那么我们就可以假设A也是C的朋友。所谓朋友圈就是所有朋友的集合。给定一个N*N的矩阵M，代表班上同学之间的友情关系。如果Mi=1，则表示已知第i个和第j个学生彼此是朋友，否则未知。你必须输出所有学生中已知朋友圈的总数。示例1：输入：[[1,1,0],[1,1,0],[0,0,1]]输出：2解释：已知学生0和学生1是彼此的朋友，他们被朋友关起来了。第二个同学在朋友圈。所以返回2。示例2：输入：[[1,1,0],[1,1,1],[0,1,1]]输出：1解释：已知学生0和学生1是朋友相互之间，学生1和学生2互为好友，所以学生0和学生2也是好友，所以三人在同一个朋友圈，返回1。注：N在[1,200范围内].对于所有学生，有M[i][i]=1。如果有M[i][j]=1，则有M[j][i]=1。DFS的思想是找出无向图中连通块的数量。访问标记。时间复杂度：O(n^2)，需要遍历M矩阵。空间复杂度：O(n)，访问数组的大小。Python3代码类解决方案：deffindCircleNum(self,M:List[List[int]])->int:m=len(M)ans,visited=0,set()#deftemplatedefdfs(i):forjinrange(m):ifM[i][j]andjnotinvisited:#1andnotvisitedvisited.add(j)dfs(j)foriinrange(m):ifinotinvisited:#1且未访问未访问dfs(i)ans+=1returnans代码地址GitHub链接
