Union Find #
- Flexibly use the idea of union find, and be proficient with the union find template. There are two implementations of union find in the template: one is the path compression + union by rank version, and the other is the version that calculates the number of elements in each set + the number of elements in the largest set. Both versions have their own use cases. Problems that can use the first type of union find template include: Problem 128, Problem 130, Problem 547, Problem 684, Problem 721, Problem 765, Problem 778, Problem 839, Problem 924, Problem 928, Problem 947, Problem 952, Problem 959, Problem 990. Problems that can use the second type of union find template include: Problem 803, Problem 952. In Problem 803, union by rank and counting the number of elements in a set may cause time limits; without optimization, it will TLE.
- Union find is an idea. Some problems require flexible use of this idea rather than rigidly applying a template, such as Problem 399. This problem is stringUnionFind, implemented using the union find idea. Here each node is based on strings and maps, rather than simply being implemented with int node numbers.
- For some problems, rigidly applying the template may make them unsolvable, such as Problem 685. This problem cannot use path compression and union by rank, because the problem involves a directed graph and needs to know each node’s predecessor. If path compression is used, this problem cannot be solved. This problem does not require path compression or union by rank.
- Flexibly abstract the information given by the problem, reasonably number the given information, use union find to solve the problem, and use maps to reduce time complexity, such as Problem 721 and Problem 959.
- For problems about maps, bricks, and grids, you can create a special node and union() the bricks or grids around the edges with this special node. Problem 130, Problem 803.
- Problems that can be solved with union find can generally also be solved with DFS and BFS, but the time complexity will be a bit higher.
| No. | Title | Solution | Difficulty | TimeComplexity | SpaceComplexity | Favorite | Acceptance |
|---|---|---|---|---|---|---|---|
| 0128 | Longest Consecutive Sequence | Go | Medium | O(n) | O(n) | ❤️ | 48.5% |
| 0130 | Surrounded Regions | Go | Medium | O(m*n) | O(m*n) | 36.7% | |
| 0200 | Number of Islands | Go | Medium | O(m*n) | O(m*n) | 57.0% | |
| 0399 | Evaluate Division | Go | Medium | O(n) | O(n) | 59.6% | |
| 0547 | Number of Provinces | Go | Medium | O(n^2) | O(n) | 63.7% | |
| 0684 | Redundant Connection | Go | Medium | O(n) | O(n) | 62.2% | |
| 0685 | Redundant Connection II | Go | Hard | O(n) | O(n) | 34.1% | |
| 0695 | Max Area of Island | Go | Medium | 71.8% | |||
| 0721 | Accounts Merge | Go | Medium | O(n) | O(n) | ❤️ | 56.3% |
| 0765 | Couples Holding Hands | Go | Hard | O(n) | O(n) | ❤️ | 56.6% |
| 0778 | Swim in Rising Water | Go | Hard | O(n^2) | O(n) | ❤️ | 59.8% |
| 0785 | Is Graph Bipartite? | Go | Medium | 53.1% | |||
| 0803 | Bricks Falling When Hit | Go | Hard | O(n^2) | O(n) | ❤️ | 34.4% |
| 0839 | Similar String Groups | Go | Hard | O(n^2) | O(n) | 48.0% | |
| 0924 | Minimize Malware Spread | Go | Hard | O(m*n) | O(n) | 42.1% | |
| 0928 | Minimize Malware Spread II | Go | Hard | O(m*n) | O(n) | ❤️ | 42.7% |
| 0947 | Most Stones Removed with Same Row or Column | Go | Medium | O(n) | O(n) | 58.9% | |
| 0952 | Largest Component Size by Common Factor | Go | Hard | O(n) | O(n) | ❤️ | 40.0% |
| 0959 | Regions Cut By Slashes | Go | Medium | O(n^2) | O(n^2) | ❤️ | 69.1% |
| 0990 | Satisfiability of Equality Equations | Go | Medium | O(n) | O(n) | 50.5% | |
| 1020 | Number of Enclaves | Go | Medium | 65.5% | |||
| 1202 | Smallest String With Swaps | Go | Medium | 57.7% | |||
| 1254 | Number of Closed Islands | Go | Medium | 64.1% | |||
| 1319 | Number of Operations to Make Network Connected | Go | Medium | 62.1% | |||
| 1579 | Remove Max Number of Edges to Keep Graph Fully Traversable | Go | Hard | 53.2% | |||
| 1631 | Path With Minimum Effort | Go | Medium | 55.7% |
中文