3 ways to solve this problem (BFS, DFS, Union Find)

• The result shows that Union Find runs the fastest.

DFS solution:

``````class Solution {
public:
using graph_t = vector<unordered_set<int>>;
int countComponents(int n, vector<pair<int, int>>& edges) {
graph_t graph(n);
int res = 0;
for (auto edge : edges) {
graph[edge.first].insert(edge.second);
graph[edge.second].insert(edge.first);
}
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(graph, visited, i);
res++;
}
}
return res;
}

void dfs(graph_t& graph, vector<bool>& visited, int v) {
if (visited[v]) return;

visited[v] = true;
for (auto w : graph[v]) {
if (!visited[w]) dfs(graph, visited, w);
}
}
};
``````

BFS:

``````class Solution {
public:
using graph_t = vector<unordered_set<int>>;
int countComponents(int n, vector<pair<int, int>>& edges) {
graph_t graph(n);
int res = 0;
for (auto edge : edges) {
graph[edge.first].insert(edge.second);
graph[edge.second].insert(edge.first);
}
vector<bool> visited(n, false);
queue<int> q;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
q.push(i);
while (!q.empty()) {
auto v = q.front(); q.pop();
visited[v] = true;
for (auto w :graph[v])
if (!visited[w]) q.push(w);
}
res++;
}
}
return res;
}
};
``````

Union Find

``````class UnionFind {
public:
UnionFind(int n) : id(n), size(n, 1), count(n) {
for (int i = 0; i < n; ++i) {
id[i] = i;
}
}

int find(int n) {
if (n != id[n]) id[n] = find(id[n]);
return id[n];
}

void combine(int i, int j) {
int p1 = find(i);
int p2 = find(j);
if (p1 == p2) return;
if (size[p1] > size[p2]) {
size[p1] += size[p2];
id[p2] = p1;
} else {
size[p2] += size[p1];
id[p1] = p2;
}
count--;
}

int getCount() {
return count;
}

private:
vector<int> id, size;
int count;
};

class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
int res = 0;
UnionFind uf(n);
for (auto edge : edges) {
uf.combine(edge.first, edge.second);
}

return uf.getCount();
}
};``````

• This post is deleted!

• Hi, Thanks for the code. Could you please explain me the first few lines of the class union find class? I am not good with classes and I do not understand what happened there? Thanks.

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