华农ACM图论算法与数据结构详解

这篇资料主要涵盖了ACM竞赛中常用的算法和数据结构，主要集中在图论、数论、数据结构以及计算几何等领域。以下是这些知识点的详细解释： 1. **图论** - **独立集**：在无向图中，一个独立集是一组不相邻的节点。目标通常是找到最大的独立集。 - **覆盖集**：图中的一组边，使得每一点至少被一条边覆盖。目标是找到最小的覆盖集。 - **支配集**：图中的一组节点，使得每个节点要么在集合内，要么与集合中的某个节点相邻。目标是找到最小的支配集。 - **DFS（深度优先搜索）**：用于遍历或搜索树或图的算法，通常用于检测环路、找到强连通分量等。 - **割顶**：如果移除一个节点会导致图中出现不连通的部分，那么这个节点就是割顶。 - **桥**：无向图中，如果去掉一条边会导致图变成不连通，这条边就是桥。 - **强连通分量**：在有向图中，如果每个节点都可以到达其他所有节点，这样的子图称为强连通分量。 2. **数论** - **最大公约数（GCD）**：两个或多个整数的最大公共因数。 - **最小公倍数（LCM）**：两个或多个整数的最小公共倍数。 - **快速幂取模**：快速计算幂并取模的算法，复杂度为O(logb)。 - **Fermat小定理**：若p是质数，a不是p的倍数，则a^(p-1) ≡ 1 (mod p)。 - **Rabin-Miller伪素数测试**：一种用于测试大整数是否为素数的概率性算法。 - **扩展欧几里德算法**：求解最大公约数的同时，找出其对应的贝祖等式解。 - **欧拉定理**：若a与m互质，a^φ(m) ≡ 1 (mod m)，其中φ(m)是欧拉函数，表示小于等于m且与m互质的正整数个数。 - **中国剩余定理**：解决一组线性同余方程的复杂数论问题。 - **Discrete Logging**：涉及指数运算在有限域上的问题。 - **N!最后一个不为0的数字**：计算阶乘最后一位非零数字。 3. **数据结构** - **堆**：一种具有特定性质的完全二叉树，常用作优先队列。包括最小堆的插入、删除最小值和建立堆的操作。 - **并查集**：用于处理集合合并与查询是否属于同一集合的问题。 - **树状数组**（又称二进制索引树）：支持区间修改和单点查询的高效数据结构。 - **线段树**：处理区间查询和修改问题的数据结构。 - **字符串**：包括字符串哈希（快速比较字符串相似性）和KMP算法（避免子串匹配中的冗余比较）。 4. **计算几何** - **直线交点**：计算两条直线的交点坐标。 - **判断线段相交**：确定两条线段是否相交。 - **三点外接圆圆心**：找到三个点构成的三角形的外接圆中心。 - **判断点在多边形内**：检测一个点是否位于多边形内部。 - **两圆交面积**：计算两个圆的交集面积。 - **最小包围圆**：寻找包含所有点的最小半径圆。 - **经纬度坐标**：处理地理坐标系统的计算。 - **凸包**：找到包含所有点的最小凸多边形。 5. **其他** - **RMQ-LCA（Range Minimum Query & Lowest Common Ancestor）**：RMQ用于查询数组中一段区间的最小值，LCA用于找到树中两个节点的最近公共祖先。两者有相互转换的方法。 以上知识点是ACM竞赛编程中必备的基础知识，理解和掌握它们对于解决算法竞赛中的各种问题至关重要。