[547. Friend Circles] C++ _ DFS and Union Find, two methods

• DFS:

`````` class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if(M.empty()) return 0;
int n = M.size();
int res = 0;
vector<bool> check(n, false);
for(int i = 0; i < n; ++i){
if(!check[i]){
dfs(M, check, i);
res++;
}
}
return res;
}

void dfs(vector<vector<int>>& M, vector<bool>& check, int i){
for(int j = 0; j < M.size(); ++j){
if(M[i][j] && !check[j]){
check[j] = true;
dfs(M, check, j);
}
}
return;
}
};
``````

Union Find:

``````class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if(M.empty()) return 0;
int n = M.size();
int res = 0;
if(n == 1) return 1;
vector<int> vec(n);
for(int i = 0; i < n; ++i){
vec[i] = i;
}
for(int i = 0; i < n - 1; ++i){
for(int j = i + 1; j < n; ++j){
if(M[i][j]){
int k = i;
while(vec[k] != k) k = vec[k];
if(k < vec[j]) {vec[k] = vec[j];}
else{vec[j] = k;}
}
}
}
for(int i = 0; i < n; ++i){
int k = i;
while(vec[k] != k) k = vec[k];
vec[i] = k;
}
unordered_set<int> st;
for(auto v : vec){
if(st.find(v) == st.end()) {res++; st.insert(v);}
}
return res;
}
};``````

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