Simple C++ DFS solution


  • 0
    T
    class Solution {
        void findCircleNum(vector<vector<int>>& M, vector<bool> &fc,int i, int n){
            for (int j = 0; j<n; j++){
                if (M[i][j] == 1 && !fc[j]){
                    fc[j] = true;
                    findCircleNum(M,fc,j,n);           
                }
            }    
        }
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int m = M.size();
            if (m == 0) return 0;
            int n = M[0].size();
            int count = 0;
            vector<bool> fc(m,false);
            for (int i=0; i<m;i++){
                  if (fc[i]) continue;
                  fc[i] = true;
                  count++;
                for (int j=0; j<n;j++){
                    if (M[i][j] == 1 && !fc[j]){
                        fc[j] = true;
                        findCircleNum(M,fc,j,n);
                    }
                }
            }
            return count;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.