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


  • 2
    R

    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();
        }
    };

  • 0
    R
    This post is deleted!

  • 0
    P

    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.


Log in to reply
 

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