图论分块

技术文章 1年前 (2020) 完美者
1,368 0

标签:class   无向图   修改   常用   更新   假设   sqrt   超过   证明   

在图论中,常常有这么一类问题,\(n\) 个点 \(m\) 条边的无向图,每次可以修改一个结点的信息,每次询问一个点邻接到的所有点的信息之和,\(n\)\(m\) 以及询问数 \(q\) 均在 \(10^5\) 这个级别。

如果直接去模拟,如果数据频繁地询问一个度数非常大的结点,显然将会 TLE。对于这种题目,有一种常用的做法是图论分块,使用了均摊复杂度的思想,时间复杂度可以达到 \(O(q\sqrt m)\)。有时图论分块还会套数据结构。

设有一张 \(n\) 个点 \(m\) 条边的无向图,不妨设度数小于等于 \(\sqrt {2m}\) 的点为轻点,度数大于 \(\sqrt {2m}\) 的点为重点,那么有以下结论:
一个轻点只与不超过 \(\sqrt {2m}\) 个点相邻,一个重点只与不超过 \(\sqrt {2m}\) 个重点相邻。

证明:假设重点 \(u\) 和多于 \(\sqrt {2m}\) 个重点相邻,那么和 \(u\) 相邻的重点度数之和将大于 \(\sqrt {2m}\times \sqrt {2m}=2m\),由握手定理,\(m\) 条边的无向图度数为 \(2m\),矛盾。所以一个重点只与不超过 \(\sqrt {2m}\) 个重点相邻。

有些博客是按 \(\sqrt m\) 划分轻重点,然后说一个重点只与不超过 \(\sqrt m\) 个重点相邻,这是错的,应该指明在渐进意义下。

那么轻点同时向相邻的轻点和重点连有向边,重点只向相邻的重点连有向边。那么每更新一个轻点,同时要维护这个轻点邻接到的所有点的信息;每更新一个重点,只维护它邻接到的重点的信息。如果询问一个重点,那么直接输出这个重点的信息;如果询问一个轻点,因为重点不会去更新轻点,所以需要暴力遍历和它相邻的所有点,计算出答案。如果修改一个点的时间复杂度是 \(O(1)\)的,那么这样单次操作的时间复杂度是 \(O(\sqrt m)\)\(q\) 次操作的时间复杂度为 \(O(q\sqrt m)\)

图论分块

标签:class   无向图   修改   常用   更新   假设   sqrt   超过   证明   

原文地址:https://www.cnblogs.com/AEMShana/p/13621787.html

版权声明:完美者 发表于 2020-09-17 16:21:52。
转载请注明:图论分块 | 完美导航

暂无评论

暂无评论...