UVa 1329

Corporative Network

from Chapter 3. Data Structures :: Fundamental Data Structures :: Examples

Problem

有N个结点，编号从1到N，一开始每个结点都没有父结点。执行以下两种操作：

• I u v：把结点u的父结点设为v，距离为|u - v| % 1000，输入保证u没有父结点。
• E u：询问u结点到根节点的距离，输出结果。

Solution

本题在并查集的基础上多了一个要求：求结点到根节点的距离。只需要维护一个数组d，保存结点到其根节点的距离，然后在并查集find操作的时候，计算d的值即可。相比带权并查集的题目要求计算任意两个结点之间的距离，本题相对容易许多。

该算法的时间复杂度为 O(N) 。