邻接表记录图 并查集查找

邻接表是一种常用的图的表示方法，它使用链表来记录每个顶点与其相邻顶点的连接关系。在邻接表中，对于每个顶点，我们创建一个链表，链表中的每个节点表示与该顶点相邻的顶点。

并查集（Disjoint Set）是一种用于处理集合合并和查找问题的数据结构。它主要支持两个操作：合并两个集合和查找某个元素所属的集合。并查集可以用来解决图的连通性问题，判断两个顶点是否在同一个连通分量中。

在记录图的邻接表时，我们可以使用数组来存储每个顶点的链表头节点，然后通过链表节点来表示与该顶点相邻的其他顶点。同时，我们可以使用并查集来实现查找操作，通过维护每个顶点所属的集合，判断两个顶点是否在同一个连通分量中。

具体实现上，可以使用一个数组来记录每个顶点的父节点，初始化时每个顶点的父节点都指向自身。当需要合并两个集合时，可以将其中一个集合的根节点指向另一个集合的根节点。而查找操作则是通过递归地找到某个元素的根节点，并返回该根节点作为该元素所属的集合的代表。

通过邻接表记录图和并查集查找，我们可以高效地处理图的连通性问题，例如判断两个顶点是否连通、计算图的连通分量个数等。