C++ || Disjoint Set Union solution Easy
Intuition\n Describe your first thoughts on how to solve this problem. \n- If the number of connections (edges) is less than n-1 (where n is the number of nodes
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- If the number of connections (edges) is less than n-1 (where n is the number of nodes), it\'s impossible to connect all computers, so we return -1.\n-  Otherwise, we use the Union-Find (Disjoint Set Union, DSU) algorithm to group computers into connected components. The goal is to find the number of disconnected components.\n-  The number of operations required to connect the network is equal to the number of components minus one (components - 1). This is because each component needs to be connected with another, requiring one operation per connection.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialization: We initialize two vectors, parent and rankk, where parent[i] points to the parent of node i, and rankk[i] helps to keep the tree flat.\n-  Find Function: This function finds the root of the set containing node x and applies path compression for efficiency.\n- Union Function: This function merges two sets by attaching the tree with the smaller rank to the root of the tree with the larger rank. If both have the same rank, we increment the rank of the resulting tree.\n- Main Function: We first check if the number of connections is sufficient. Then, we iterate through each connection and merge the sets of the connected nodes, reducing the number of components when a new connection is made.\n- Result: The number of operations required is the number of remaining components minus one.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(E * \u03B1(N))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N)\n\n# Code\n```\nclass Solution {\nprivate:\n    vector<int> parent; // To store the parent of each node\n    vector<int> rankk;  // To store the rank (depth) of each tree\n\n    // Find function with path compression\n    int find(int x) {\n        if (parent[x] != x) {\n            parent[x] = find(parent[x]); // Path compression\n        }\n        return parent[x];\n    }\n\n    // Union function with union by rank\n    void unionSet(int x, int y) {\n        x = find(x); // Find root of x\n        y = find(y); // Find root of y\n\n        if (rankk[x] < rankk[y]) {\n            parent[x] = y; // Attach smaller rank tree under larger rank tree\n        } else if (rankk[x] > rankk[y]) {\n            parent[y] = x;\n        } else {\n            parent[y] = x; // Attach one tree under another and increase rank\n            rankk[x]++;\n        }\n    }\n\npublic:\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        int components = n; // Initially, assume all nodes are separate components\n        parent.resize(n);    // Resize parent vector to accommodate n nodes\n        rankk.resize(n, 0);  // Initialize rank vector with 0\n\n        // If there are not enough connections to connect all nodes, return -1\n        if (connections.size() < n - 1) return -1;\n\n        // Initially, every node is its own parent\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n\n        // Process each connection\n        for (auto& vec : connections) {\n            // If the nodes are not already connected, connect them\n            if (find(vec[0]) != find(vec[1])) {\n                unionSet(vec[0], vec[1]);\n                components--; // Decrease the number of components\n            }\n        }\n\n        // Return the number of operations needed to connect all components\n        return components - 1;\n    }\n};\n```
['C++']