Disjoint set Using Rank
Intuition\nWhen attempting to connect all computers in a network with given cables, the core problem is identifying whether there are enough cables to connect a
# Intuition\nWhen attempting to connect all computers in a network with given cables, the core problem is identifying whether there are enough cables to connect all isolated components. This problem can be approached using the Disjoint Set Union (DSU) data structure to efficiently manage and merge components.\n\n# Approach\n1. **Initialize Disjoint Set:**\n   - Create a Disjoint Set with rank and parent arrays to manage the connections.\n   \n2. **Process Connections:**\n   - Iterate over each connection. Use the DSU to determine if two nodes are already connected.\n   - If they are already connected, increment the count of extra connections.\n   - If not, unite the two nodes.\n   \n3. **Count Connected Components:**\n   - Iterate over all nodes to count how many distinct components are present by checking the parent array.\n   \n4. **Determine Feasibility:**\n   - If the number of extra connections is greater than or equal to the number of components needed to be connected minus one, return the number of operations required (which is the number of components minus one).\n   - Otherwise, return -1, indicating it\'s not possible to connect all components with the given cables.\n\n# Complexity\n- **Time Complexity:** \\(O(n + m)\\) where \\(n\\) is the number of nodes and \\(m\\) is the number of connections. The operations on DSU (find and union) are nearly constant time due to path compression and union by rank.\n- **Space Complexity:** \\(O(n)\\) for storing parent and rank arrays.\n\n# Code\n```cpp\nclass DisjointSet {\npublic:\n    vector<int> rank, parent;\n\n    DisjointSet(int n) {\n        rank.resize(n + 1, 0);\n        parent.resize(n + 1);\n        for (int i = 0; i <= n; i++) parent[i] = i;\n    }\n\n    int findUltimateParent(int node) {\n        if (node == parent[node]) return node;\n        return parent[node] = findUltimateParent(parent[node]);\n    }\n\n    void unionByRank(int node1, int node2) {\n        int parent1 = findUltimateParent(node1);\n        int parent2 = findUltimateParent(node2);\n\n        if (parent1 == parent2) return;\n        if (rank[parent1] < rank[parent2]) {\n            parent[parent1] = parent2;\n        } else if (rank[parent2] < rank[parent1]) {\n            parent[parent2] = parent1;\n        } else {\n            parent[parent2] = parent1;\n            rank[parent1]++;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        int no_of_connected_components = 0;\n        int extra_connections = 0;\n\n        DisjointSet ds(n);\n\n        for (auto& it : connections) {\n            int u = it[0];\n            int v = it[1];\n\n            if (ds.findUltimateParent(u) == ds.findUltimateParent(v)) {\n                extra_connections++;\n            } else {\n                ds.unionByRank(u, v);\n            }\n        }\n\n        for (int i = 0; i < n; i++) {\n            if (ds.parent[i] == i) {\n                no_of_connected_components++;\n            }\n        }\n\n        if (no_of_connected_components - 1 <= extra_connections) {\n            return no_of_connected_components - 1;\n        }\n\n        return -1;\n    }\n};\n```\n\n
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Graph', 'C++']