0

由n 个节点组成的图,其中有一条边从122334、 ........、n-1n

现在,有一个由1n的排列组成的数组,并且有基于数组段给出的查询数量。确定给定段的节点(由数组元素指示)形成的连通分量的数量。例如,

数组:4 5 3 2 1 查询是:[1, 5] , [1, 4] , [2, 4]

对于[1, 5],数组元素是1 2 3 4 5并且所有元素都是连接的并形成单个连接组件。

对于[1, 4],数组元素是2 3 4 5,它们也形成了单个连通分量。

对于[2, 4],数组元素是2 3 5,因此23形成单个组件,而5形成单个组件,因此[2, 4]中共有2 个连接的组件。

4

1 回答 1

1

由于图没有环,因此子图中的分量数等于顶点数减去边数。顶点数就是查询区间的长度。边的数量可以通过构造一个用于 2D 正交范围计数查询的预言来快速找到,这些查询对所有 k 的点 (k 在排列中的位置,k+1 在排列中的位置) 进行。

于 2016-10-23T13:54:46.753 回答