[C++/Java/Python] Union Find - Feel free to reuse! - Clean & Concise - O(N)
Idea\n- A valid tree is an undirected graph which has exactly N-1 edges to connect N vertices in the tree.\n- Since the given tree has a redundant edge, so ther
**Idea**\n- A valid tree is an undirected graph which has exactly `N-1` edges to connect `N` vertices in the tree.\n- Since the given tree has a redundant edge, so there is `N` edges in the given input.\n- Number of vertices `N = len(edges)`.\n- There is a data structure called [UnionFind or Disjoint-set](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) which has 2 basic operations:\n\t- `uf.find(u)`, which outputs a unique id so that two nodes have the same id if and only if they are in the same connected component.\n\t- `uf.union(u, v)`, which connects the components with id `find(u)` and `find(v)` together. If it already connected then return False, else return True.\n- Then we iterate edge `[u, v]` in `edges`, if `u` and `v` is already connected in the UnionFind then we return that redundant edge.\n\n**Implementation**\n<iframe src="https://leetcode.com/playground/j33hRwjo/shared" frameBorder="0" width="100%" height="720"></iframe>\n\n**Complexity**\n- Time: `O(N * \u03B1(N))`, where `N` is number of vertices in the graph.\n  Explanation: Using both **path compression** and **union by size** ensures that the **amortized time** per **UnionFind** operation is only `\u03B1(n)`, which is optimal, where `\u03B1(n)` is the inverse Ackermann function. This function has a value `\u03B1(n) < 5` for any value of n that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time.\nReference: https://en.wikipedia.org/wiki/Disjoint-set_data_structure or https://www.slideshare.net/WeiLi73/time-complexity-of-union-find-55858534 for more information.\n- Space: `O(N)`\n\n**Practice more on UnionFind topics**\n- [1319. Number of Operations to Make Network Connected](https://leetcode.com/problems/number-of-operations-to-make-network-connected/discuss/477660)\n- [721. Accounts Merge](https://leetcode.com/problems/accounts-merge/)\n- [1627. Graph Connectivity With Threshold](https://leetcode.com/problems/graph-connectivity-with-threshold/)\n\nIf you **have any questions, feel free to comment below**, I will try my best to answer. If you think this post is useful, I\'m happy if you **give it a vote**. Thanks.
[]