关于级联的题很多，官方数据是30个（截至2020-02-20），但也有一些题目官方没有给级联打上标签。使用unionlookup确实很简单。如果你掌握了这类题的模板，你就能很快的做完这类题，做错的概率也会大大降低。这就是模板的好处。这里我总结了几道题，收集起来：547.Moments721.AccountMerger990.EquationSatisfiability以上三道题大家可以学习模板套用。如果你做不到，你可以看到它。查看我的解决方案。Union-Find算法是Union-Find算法的概述，主要解决图论中的“动态连通性”问题。Union-Find算法解决了图的动态连通性问题。这个算法本身并不难。能不能应用主要看你自己。问题抽象能力，原问题能否抽象成图论问题。如果对这个算法不是很了解，推荐看这篇Union-Find算法详解，非常详细。可以把联合搜索的元素看成部门里的人，几个人可以组成多个部门。搜索和收集的三个核心方法是union、find和connected。union：将两个人的两个部门合并为一个部门（如果两个人在同一个部门，实际的山不需要合并）（图片来自labuladong）find：找到某人的部门leaderconnected：判断两个人是否属于同部门（图片来自labuladong）Template这是我经常用到的一个模板。我会根据具体题目做小改动，但大体上是一样的。classUF:parent={}cnt=0def__init__(self,M):#初始化父级和cntdeffind(self,x):whilex!=self.parent[x]:x=self.parent[x]returnxdefunion(self,p,q):ifself.connected(p,q):returnself.parent[self.find(p)]=self.find(q)self.cnt-=1defconnected(self,p,q):returnself.find(p)==self.find(q)如果你想要更好的性能，这个模板更适合你，相应的代码也稍微复杂一点。classUF:parent={}size={}cnt=0def__init__(self,M):#初始化父级、size和cntdeffind(self,x):whilex!=self.parent[x]:x=self.parent[x]#路径压缩self.parent[x]=self.parent[self.parent[x]];returnxdefunion(self,p,q):ifself.connected(p,q):return#把小树挂在大树上，让树尽量平衡leader_p=self.find(p)leader_q=self.find(q)如果self.size[leader_p]
