Leetcode 547. Friend Circles

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int rows = M.size();
        int flag[rows] = {0};
        int count = 0;
        for(int i = 0; i < rows; i++) {
            if(!flag[i]) {
                ++count;
                queue<int> friends;
                friends.push(i);
                oneCircle(M, flag, friends);
            }
        }
        return count;
    }
    
    void oneCircle(vector<vector<int>>& M, int flag[], queue<int> friends) {
        int rows = M.size();
        while(!friends.empty()) {
            int row = friends.front();
            friends.pop();
            for(int i = 0; i < rows; i++) {
                if(M[row][i] && i != row && !flag[i]) {
                    flag[i] = 1;
                    friends.push(i);
                }
            }
        }
    }
};

Reference

1. https://leetcode.com/problems/friend-circles/description/