并查集

假设你需要为$n$个城市铺设光缆，每两个城市之间的铺设成本各不相同。如何用最低的总成本让所有城市互联互通？这看似是一个复杂的优化问题，实际上可以抽象为图论中的经典问题——最小生成树（Minimum Spanning Tree，简称MST）。 ...

假设你正在开发一个社交网络应用，需要实时回答"用户A和用户B是否在同一个社交圈内"这类查询——用户之间可以通过好友关系不断形成更大的圈子。每添加一个好友关系，圈子就可能合并；每查询一次，就需要判断两个用户是否已经连通。如果用传统的图遍历方法，每次查询都可能需要遍历整个图，当用户量达到百万级别时，系统会变得极其缓慢。 ...