# [547\. Number of Provinces](https://leetcode.com/problems/number-of-provinces/)

:::spoiler Hint

class UnionFind {
private:
    // Stores the parent of each node
    // Stores the rank (size) of each tree

public:
    // Constructor to initialize the Union-Find data structure
    UnionFind()
    {
        // Resize parent vector to hold n elements
        // Initialize rank vector with 1 for each node
        for ()
        {
            // Initially, each node is its own parent
        }
    }

    // Find the root of the set containing x, with path compression
    int find(int x)
    {
    }
    
    // Union the sets containing n1 and n2
    void unionNodes(int n1, int n2)
    {
        // Find the root of the set containing n1
        // Find the root of the set containing n2

        // If both nodes are already in the same set, do nothing
        
        // Union by rank
        if ()
        {
            // Make p1 the root of p2
            // Update the rank of the new root
        }
        else
        {
            // Make p2 the root of p1
            // Update the rank of the new root
        }
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected)
    {
        // Initialize the Union-Find data structure

        // Start with the assumption that there are n disconnected components
        for ()
        {
            for ()
            {
                if ()
                {
                    // If i and j are connected and belong to different components, decrement count
                    // Union the components of i and j
                }
            }
        }
        // Return the number of connected components
    }
};

:::

:::spoiler Solution - Union Find

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

    int find(int x)
    {
        if (x != parent[x])
        {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unionNodes(int n1, int n2)
    {
        int p1 = find(n1);
        int p2 = find(n2);

        if (p1 == p2) return;
        
        if (rank[p1] > rank[p2])
        {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        }
        else
        {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected)
    {
        int n = isConnected.size();
        UnionFind uf(n);

        int cnt = n;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (isConnected[i][j] && uf.find(i) != uf.find(j))
                {
                    cnt--;
                    uf.unionNodes(i, j);
                }
            }
        }
        return cnt;        
    }
};

- T: $O(n^2)$
- S: $O(n)$
:::