323. Number of Connected Components in an Undirected Graph

Union Find

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int size)
    {
        parent.resize(size);
        rank.resize(size, 1);
        for (int i = 0; i < size; ++i)
        {
            parent[i] = i;
        }
    }

    int find(int node)
    {
        if (parent[node] != node)
        {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    void unionNodes(int node1, int node2)
    {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) return;
        if (rank[root1] < rank[root2])
        {
            parent[root1] = root2;
        }
        else if (rank[root1] > rank[root2])
        {
            parent[root2] = root1;
        }
        else
        {
            parent[root2] = root1;
            rank[root1]++;
        }
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges)
    {
        UnionFind uf(n);

        for (const auto& edge : edges)
        {
            uf.unionNodes(edge[0], edge[1]);
        }

        int count = 0;

        for (int i = 0; i < n; ++i)
        {
            if (uf.find(i) == i)
            {
                ++count;
            }
        }
        return count;
    }
};

• T: $O(E + V)$
• S: $O(E + V)$

DFS

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges)
    {
        int count = 0;
        vector<bool> seen(n);
        vector<vector<int>> graph(n);

        for (auto edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        for (int i = 0; i < n; ++i)
        {
            if (!seen[i])
            {
                ++count;
                dfs(graph, seen, i);
            }
        }
        return count;
    }
    void dfs(vector<vector<int>>& graph, vector<bool>& seen, int node)
    {
        if (seen[node]) return;

        seen[node] = true;
        for (int i = 0; i < graph[node].size(); ++i)
        {
            dfs(graph, seen, graph[node][i]);
        }
    }
};

• T: $O(E + V)$
• S: $O(E + V)$