Union Find

+++ author = "一缕殇流化隐半边冰霜" categories = ["Algorithm", "Union Find"] date = 2019-11-16T08:31:00Z description = "" draft = false image = "https://img.halfrost.com/Blog/ArticleTitleImage/142_0.png" slug = "union_find" tags = ["Algorithm", "Union Find"] title = "Algorithm in LeetCode —— Union Find"

+++

Union Find 的 Tips:

• 灵活使用并查集的思想，熟练掌握并查集的模板，模板中有两种并查集的实现方式，一种是路径压缩 + 秩优化的版本，另外一种是计算每个集合中元素的个数 + 最大集合元素个数的版本，这两种版本都有各自使用的地方。能使用第一类并查集模板的题目有：第 128 题，第 130 题，第 547 题，第 684 题，第 721 题，第 765 题，第 778 题，第 839 题，第 924 题，第 928 题，第 947 题，第 952 题，第 959 题，第 990 题。能使用第二类并查集模板的题目有：第 803 题，第 952 题。第 803 题秩优化和统计集合个数这些地方会卡时间，如果不优化，会 TLE。
• 并查集是一种思想，有些题需要灵活使用这种思想，而不是死套模板，如第 399 题，这一题是 stringUnionFind，利用并查集思想实现的。这里每个节点是基于字符串和 map 的，而不是单纯的用 int 节点编号实现的。
• 有些题死套模板反而做不出来，比如第 685 题，这一题不能路径压缩和秩优化，因为题目中涉及到有向图，需要知道节点的前驱节点，如果路径压缩了，这一题就没法做了。这一题不需要路径压缩和秩优化。
• 灵活的抽象题目给的信息，将给定的信息合理的编号，使用并查集解题，并用 map 降低时间复杂度，如第 721 题，第 959 题。
• 关于地图，砖块，网格的题目，可以新建一个特殊节点，将四周边缘的砖块或者网格都 union() 到这个特殊节点上。第 130 题，第 803 题。
• 能用并查集的题目，一般也可以用 DFS 和 BFS 解答，只不过时间复杂度会高一点。

Title	Solution	Difficulty	Time	Space	收藏
128. Longest Consecutive Sequence	Go	Hard	O(n)	O(n)	❤️
130. Surrounded Regions	Go	Medium	O(m*n)	O(m*n)
200. Number of Islands	Go	Medium	O(m*n)	O(m*n)
399. Evaluate Division	Go	Medium	O(n)	O(n)
547. Friend Circles	Go	Medium	O(n^2)	O(n)
684. Redundant Connection	Go	Medium	O(n)	O(n)
685. Redundant Connection II	Go	Hard	O(n)	O(n)
721. Accounts Merge	Go	Medium	O(n)	O(n)	❤️
765. Couples Holding Hands	Go	Hard	O(n)	O(n)	❤️
778. Swim in Rising Water	Go	Hard	O(n^2)	O(n)	❤️
803. Bricks Falling When Hit	Go	Hard	O(n^2)	O(n)	❤️
839. Similar String Groups	Go	Hard	O(n^2)	O(n)
924. Minimize Malware Spread	Go	Hard	O(m*n)	O(n)
928. Minimize Malware Spread II	Go	Hard	O(m*n)	O(n)	❤️
947. Most Stones Removed with Same Row or Column	Go	Medium	O(n)	O(n)
952. Largest Component Size by Common Factor	Go	Hard	O(n)	O(n)	❤️
959. Regions Cut By Slashes	Go	Medium	O(n^2)	O(n^2)	❤️
990. Satisfiability of Equality Equations	Go	Medium	O(n)	O(n)