leetcode547 朋友圈

题目

朋友圈

分析

由题目知，每一个人都有一些朋友，朋友的朋友也是我的朋友，把这些朋友串联起来可以组成一个圈就是朋友圈。

解法：

• 一开始我们不知道有几个朋友圈，所以朋友圈个数为0，并且每个人都不在朋友圈里。
• 遍历到第一个人，发现他还不属于任何一个朋友圈，那么他必定属于一个新的朋友圈，所以朋友圈个数加一。
• 然后根据关系，将他所在的朋友圈的人全部找出来标记，这些标记的人以后再遍历到的时候，我们就知道他已经属于一个我们已经找到的朋友圈了。这一步用dfs来做。
• 重复以上步骤直到遍历所有人。

代码

class Solution {
private:
    int res;
    vector<int> bo;
        
    void dfs(int k, vector<vector<int>>& nums){
        for (int i = 0; i < nums.size(); i++){
            if (nums[k][i] == 1 && bo[i] == 0){
                bo[i] = 1;
                dfs(i, nums);
            }
        }
    }
public:
    int findCircleNum(vector<vector<int>>& nums) {

        bo = vector(nums.size(), 0);
        res = 0;

        for (int i = 0; i < nums.size(); i++){
            if (bo[i] == 0){
                res++;
                dfs(i, nums);
            }
        }

        return res;
    }
};