# [C++] Clean Code - DFS|UnionFind

• DFS

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

private:
int dfs(int i, vector<vector<int>>& M, vector<bool>& visited) {
if (visited[i]) {
return 0;
}

int ppl = 1;
visited[i] = true;
for (int j = 0; j < visited.size(); j++) {
if (i != j && M[i][j]) {
ppl += dfs(j, M, visited);
}
}

return ppl;
}
};
``````

Could be shorter. If the dfs() doesn't care how many people in each group;

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

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

UnionFind

``````class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if (M.empty()) return 0;
int n = M.size();

for (int i = 0; i < n; i++) { leads[i] = i; }   // initialize leads for every kid as themselves

int groups = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {   // avoid recalculate M[i][j], M[j][i]
if (M[i][j]) {
if (lead1 != lead2) {       // if 2 group belongs 2 different leads, merge 2 group to 1
groups--;
}
}
}
}
return groups;
}

private:
int find(int x, vector<int>& parents) {
return parents[x] == x ? x : find(parents[x], parents);
}
};
``````

• Its giving wrong answer for following test case
[[1,1,0],[1,1,0],[0,0,0]]

• @priyanka said in [C++] Clean Code:

Its giving wrong answer for following test case
[[1,1,0],[1,1,0],[0,0,0]]

You must see this:

It is giving the right answer which is 2. The test implementation was wrong, it shouldn't be 1.

in this test case, student_0 and student_1 knows each other, student_2 doesn't know any other. So there is 2 group: {0, 1} and {2}.

This problem is not trying to find number of islands in the matrix.

• @alexander isn't this problem finding islands in a matrix?i'm confused since isn't 2 the number of islands in this test case matrix?

• @priyanka The input [[1,1,0],[1,1,0],[0,0,0]] is not valid. The description of the problem says M[i][i] = 1 for all students. The [0,0,0] have to be [0,0,1].

• whats the purpose of visited array ?. It keeps track which rows we have visited till now or which columns for a particular row ? i believe rows but wanted to confirm

• @alexander i think it is similar to isolated island problem

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