题目

https://leetcode-cn.com/problems/friend-circles/

朋友圈.png

简析

矩阵遍历问题，循环判断所有小朋友，即从对角线点出发

• 如果这个点是1，说明这个小朋友还没有属于任何一个朋友圈，朋友圈总数+1，从这个小朋友开始搜索，把他的朋友圈全都标记成2.
• 如果这个点是2，则这个小朋友已经属于了某个朋友圈，不用再做任何操作

1） for循环范围

判断某个小朋友，自然要把这个小朋友的所有朋友找出来，行是传入的K，列是从第一列，到最后一列。

for(int j=0;j<M.size();j++)//1 确定for循环范围，扫描第k个人的朋友圈

2) 判断是否满足条件

• 为1就可以，是朋友,继续搜
• 为0就不是，什么都不用做

if(M[k][j]==1)

3）满足条件后如何

如此时是0行，0和1是朋友，则把（0，1），（1，1）这个两个点设为2，然后搜索1号小朋友。

• 把找到的小朋友对应对角线元素设为2
• 把这个点设为2，之后不再判断
• 搜索找到的小朋友

if(M[k][j]==1){
           M[k][j]=2;
           M[j][j]=2;
           search(M,j);
}

4)主函数

主函数从第一个小朋友开始，遍历每一个小朋友，即对角线元素

• 如果为1，朋友圈数+1，从它开始搜索
• 不为1，说明已经属于某个朋友圈了并且已经搜索过了

完整代码

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int count=0;
        for(int i=0;i<M.size();i++){
                if(M[i][i]==1){
                    count++;
                    M[i][i]=2;
                    search(M,i);
                }
        }
        return count;
    }
    void search(vector<vector<int>>& M,int k){
        for(int j=0;j<M.size();j++)//1 确定for循环范围，扫描第k个人的朋友圈
        {
            if(M[k][j]==1){
                M[k][j]=2;
                M[j][j]=2;
                search(M,j);
            }
        }
    }
};