Leetcode 323 Solution

This article provides solution to leetcode question 323 (number-of-connected-components-in-an-undirected-graph)
Categories:
Tags:
Access this page by simply typing in "lcs 323" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph

Solution

class FindAndUnionSet
{
    int* a;

public:
    FindAndUnionSet(int n)
    {
        a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i;
    }

    void Union(int i, int j)
    {
        int pi = Find(i);
        int pj = Find(j);
        a[pi] = pj;
    }

    int Find(int i)
    {
        return i == a[i] ? i : a[i] = Find(a[i]);
    }
};

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        FindAndUnionSet s(n);

        for (auto edge : edges)
            s.Union(edge.first, edge.second);

        unordered_set<int> roots;
        for (int i = 0; i < n; i++)
            roots.insert(s.Find(i));

        return roots.size();
    }
};