C++ STRIVER EASY  SOLUTION
Intuition\n - The problem can be visualized as finding the minimum number of connections needed to make all nodes in a graph connected. We can use a Disjoint Se
# Intuition\n - The problem can be visualized as finding the minimum number of connections needed to make all nodes in a graph connected. We can use a Disjoint Set (Union-Find) data structure to efficiently manage and union the components of the graph. If we find more connections than necessary (extras), these can help us connect disjoint components.\n\n# Approach\n- Initialize a Disjoint Set to manage the connectivity of nodes.\nIterate over each connection. If the nodes of a connection already have the same parent, count it as an extra connection. Otherwise, union the sets of the two nodes.\n- After processing all connections, count the number of connected components by checking the unique parents.\nCalculate the minimum number of connections needed to connect all components.\n-  This is the number of connected components minus one.\nIf the number of extra connections is greater than or equal to the required connections, return the required number of connections. Otherwise, return -1.\n\n# Complexity\n# Time Complexity\n\nO(n+m\u22C5\u03B1(n)), where n is the number of nodes, \nm is the number of connections, and \n\u03B1 is the inverse Ackermann function which is very slow-growing and can be considered almost constant.\n\n\n\n# Space complexity:\n- The space complexity is \nO(n) for storing the parent, rank, and size arrays in the Disjoint Set.\n\n# Code\n```\n// User function Template for C++\n\nclass DisjointSet {\npublic:\n    vector<int> parent, rank, size;\n\n    // Constructor to initialize the Disjoint Set\n    DisjointSet(int n) {\n        rank.resize(n + 1, 0);  // Initialize rank array with 0\n        size.resize(n + 1, 1);  // Initialize size array with 1\n        parent.resize(n + 1);   // Initialize parent array\n        for (int i = 0; i <= n; i++) {  // Initialize each node to be its own parent\n            parent[i] = i;\n        }\n    }\n\n    // Function to find the ultimate parent of a node with path compression\n    int findUPar(int node) {\n        if (node == parent[node]) return node;  // If the node is its own parent, return the node\n        return parent[node] = findUPar(parent[node]);  // Path compression\n    }\n\n    // Function to union two sets by rank\n    void unionByRank(int u, int v) {\n        int ulp_u = findUPar(u);  // Find ultimate parent of u\n        int ulp_v = findUPar(v);  // Find ultimate parent of v\n        if (ulp_u == ulp_v) return;  // If they are already in the same set, do nothing\n\n        // Union by rank\n        if (rank[ulp_u] < rank[ulp_v]) {\n            parent[ulp_u] = ulp_v;  // Make ulp_v the parent of ulp_u\n        } else if (rank[ulp_u] > rank[ulp_v]) {\n            parent[ulp_v] = ulp_u;  // Make ulp_u the parent of ulp_v\n        } else {\n            parent[ulp_v] = ulp_u;  // If ranks are equal, make one root and increase its rank\n            rank[ulp_u]++;\n        }\n    }\n\n    // Function to union two sets by size\n    void unionBySize(int u, int v) {\n        int ulp_u = findUPar(u);  // Find ultimate parent of u\n        int ulp_v = findUPar(v);  // Find ultimate parent of v\n        if (ulp_u == ulp_v) return;  // If they are already in the same set, do nothing\n\n        // Union by size\n        if (size[ulp_u] < size[ulp_v]) {\n            parent[ulp_u] = ulp_v;  // Make ulp_v the parent of ulp_u and update size\n            size[ulp_v] += size[ulp_u];\n        } else {\n            parent[ulp_v] = ulp_u;  // Make ulp_u the parent of ulp_v and update size\n            size[ulp_u] += size[ulp_v];\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        DisjointSet ds(n);  // Initialize Disjoint Set for n nodes\n\n        int cntExtras = 0;  // Count of extra connections\n        for (auto it : connections) {\n            int u = it[0];\n            int v = it[1];\n            if (ds.findUPar(u) == ds.findUPar(v)) {\n                cntExtras++;  // If u and v are already connected, it\'s an extra connection\n            } else {\n                ds.unionBySize(u, v);  // Otherwise, union the sets containing u and v\n            }\n        }\n\n        int cntC = 0;  // Count of connected components\n        for (int i = 0; i < n; i++) {\n            if (ds.findUPar(i) == i) cntC++;  // If node is its own parent, it\'s a unique component\n        }\n\n        int ans = cntC - 1;  // Minimum number of connections required to connect all components\n        if (cntExtras >= ans) return ans;  // If we have enough extra connections, return the answer\n        return -1;  // Otherwise, return -1 (not possible to connect all components)\n    }\n};\n\n```
['C++']