number-of-connected-components-in-an-undirected-graph

Description

Solution

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<int> dp(n, -1);
        vector<bool> occupied(n);
        int ret = n;
        for (int i = 0; i < n; ++i) dp[i] = i;
        for (int i = 0; i < edges.size(); ++i) {
            int left = edges[i].first;
            int right =edges[i].second;
            int leftRoot = findRoot(dp, left);
            int rightRoot = findRoot(dp, right);
            if (leftRoot != rightRoot) {
                dp[leftRoot] = rightRoot;
                --ret;
            }
        }
        
        return ret;
    }
    

    int findRoot(vector<int>& dp, int index) {
        stack<int> st;
        while (dp[index] != index) {
            st.push(index);
            index = dp[index];
        }
        while(st.empty() == false) {
            int item = st.top();
            dp[item] = index;
            st.pop();
        }
        return index;
    }
};