Union-Find: Missing Connections
We connect computers using Union-Find. If two computers are already in the same connected group, we have an extra cable (++extra_cables).\n\nUpdate: as SleepyFa
We connect computers using Union-Find. If two computers are already in the same connected group, we have an extra cable (`++extra_cables`).\n\n**Update:** as [SleepyFarmer](https://leetcode.com/sleepyfarmer) observed below, we can connect all `n` computers if we have at least `n - 1` total cables. So, we can check this in the beginning return `-1` right away if we do not have enough cables.\n\nInitially, `n` computers need to be connected. If computers are in the different groups, we connect them and decrease `n`. In the end, we need to connect the remaining `n - 1` computers. \n\n**Update:** I am now using rank (as number of elements in the group) to join smaller group into a larger one, and the runtime complexity went down to 88 ms from 104 ms. Note than the rank is typically the "depth" of the tree, but with path compression "depth" becomes one. So, my recommendation is to use number of elements as a proxy for the rank if you use the path compression.\n\n```CPP\nint find(vector<int> &ds, int i) {\n    return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);\n}\nint makeConnected(int n, vector<vector<int>>& connections) {\n    if (connections.size() < n - 1) return -1;\n    vector<int> ds(n, -1);\n    for (auto &c : connections) {\n        auto i = find(ds, c[0]), j = find(ds, c[1]);\n        if (i != j) {\n            if (ds[j] < ds[i])\n                swap(i, j);\n            ds[i] += ds[j];\n            ds[j] = i;\n            --n;\n        }\n    }\n    return n - 1;\n}\n```\n**Complexity Analysis**\n- Time: O(m), where `m` is the number of connections (union operations). Since we are using the path compression, a single union operation is O(log*(m)) per [this Wikipedia article](https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find). With ranking, it is O(\u03B1(m)), where \u03B1 is the inverse of the Ackerman function. For practical purposes, we can consider \u03B1(m) a constant. So, we are performing `m` operations, each taking a constant time. \n- Memory: O(n) for the disjoint set.
[]