Leetcode[547] Friend Circles

Solution I. BFS (Time: O(N^2))

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        int count = 0;
        unordered_map<int, int> unvisited;
        for(int i = 0; i < n; i++){
            unvisited[i] = i;
        }
        while(!unvisited.empty()){
            auto it = unvisited.begin();
            int p = it->second;
            unvisited.erase(p);
            queue<int> circle;
            circle.push(p);
            while(!circle.empty()){
                p = circle.front();
                for(int i = 0; i < n; i++){
                    if(M[p][i] == 1 && unvisited.find(i) != unvisited.end()) {
                        circle.push(i);
                        unvisited.erase(i);
                    }
                }
                circle.pop();
            }
            count++;
        }
        return count;
    }  
};

Note: I used unordered_map here to easily erase entry by value. vector does not support this function

Union Find (Loop half matrix)

class Solution {
    
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        vector<int> P(n, -1);
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                if(M[i][j] == 1) {
                    union1(i, j, P);
                }
            }
        }
        int count = 0;
        for(int i = 0; i < n; i++) {
            if(P[i] == -1) count++;
        }
        return count;
    }
    
    int find(int i, vector<int>& P) {
        if(P[i] == -1) return i;
        return find(P[i], P);
    }
    
    void union1(int i, int j, vector<int>& P) {
        int pi = find(i, P);
        int pj = find(j, P);
        if(pi == pj) return;
        P[pi] = pj;
    }
};

Note: union is a reserved key in c++