如何采集网站文章攻击网站步骤

如何采集网站文章,攻击网站步骤,网站开发图,网站建设公司能信吗目录 前言 一、并查集是什么#xff1f;—— 一句话看懂核心本质 二、并查集的核心原理 —— 数组如何模拟 “圈子”#xff1f; 2.1 父指针数组的规则 初始状态#xff08;10 个独立集合#xff09; 一次合并#xff08;形成三个小分队#xff09; 第二次合并—— 一句话看懂核心本质二、并查集的核心原理 —— 数组如何模拟 “圈子”2.1 父指针数组的规则初始状态10 个独立集合一次合并形成三个小分队第二次合并西安 成都小分队2.2 核心操作的原理1查找Find找到元素的根节点2合并Union将两个集合合并为一个3统计集合个数Count统计当前不相交集合的数量2.3 并查集的优化 —— 路径压缩Find 操作的终极优化路径压缩的原理三、并查集的 C 实现 —— 完整代码与详细注释3.1 基础实现带路径压缩和按大小合并3.2 代码解释3.3 递归实现路径压缩可选四、并查集的经典应用场景 —— 面试高频题实战4.1 应用一省份数量LeetCode 547题目描述示例解题思路C 代码实现代码优化点4.2 应用二等式方程的可满足性LeetCode 990题目描述示例解题思路C 代码实现关键思路4.3 应用三其他常见场景五、并查集的时间复杂度与空间复杂度分析5.1 时间复杂度5.2 空间复杂度六、并查集的常见误区与注意事项6.1 常见误区6.2 注意事项总结前言在编程世界里有一类问题始终困扰着初学者 —— 如何高效处理元素的分组、合并与查询比如判断社交网络中的 “朋友圈” 数量、验证等式方程的可满足性、解决图的连通分量问题等。如果用常规的暴力方法不仅代码繁琐效率也会大打折扣。而并查集Union-Find Set这个看似简单却极具智慧的数据结构正是为解决这类问题而生。它就像一个 “社交圈子管理器”能轻松实现 “查找某人属于哪个圈子” 和 “将两个圈子合并” 这两个核心操作且经过优化后这两个操作的时间复杂度几乎能达到常数级别。本文将从原理入手带你层层揭开并查集的神秘面纱让你从 “入门” 到 “精通”再到 “实战应用”真正掌握这个面试与工作中的 “利器”。下面就让我们正式开始吧一、并查集是什么—— 一句话看懂核心本质并查集也叫 disjoint-set不相交集合是一种支持快速查找和合并操作的抽象数据类型主要用于处理一系列不相交集合的合并与查询问题。它的核心思想可以用生活中的 “朋友圈” 来理解初始时每个人都是一个独立的 “小圈子”单元素集合当两个人成为朋友时他们所在的 “小圈子” 就会合并成一个 “大圈子”集合合并当我们想知道两个人是否是朋友时只需判断他们是否在同一个 “圈子” 里集合查询。再举一个更具体的例子某公司校招了 10 名新员工编号 0-9来自不同城市起初互不相识每个员工自成一个集合。后来西安的 4 名员工0、6、7、8组成小分队成都的 3 名员工1、4、9组成小分队武汉的 3 名员工2、3、5组成小分队三次集合合并。之后西安的 8 号员工和成都的 1 号员工成为好友两个小分队又合并成一个大圈子第四次合并。我们需要快速回答“3 号和 7 号是否在同一个圈子”“现在总共有多少个圈子”—— 这些问题并用查集都能高效解决。简单来说并查集就是管理 “圈子” 的数据结构核心支持三个操作查找Find、合并Union、统计集合个数Count。二、并查集的核心原理 —— 数组如何模拟 “圈子”并查集的实现非常巧妙通常用一个数组就能模拟所有集合的关系。这个数组我们称之为“父指针数组”记为ufsUnion-Find Set 的缩写数组的下标对应元素的编号数组的值则有特殊含义2.1 父指针数组的规则若ufs[index] 0表示index是一个集合的根节点“圈子的首领”其绝对值|ufs[index]|表示该集合的元素个数若ufs[index] 0表示index不是根节点其值指向该元素的“父节点”同一个圈子里的上一级成员。我们用之前的员工例子来直观理解初始状态10 个独立集合每个员工都是自己的 “首领”集合大小为 1所以数组所有元素都为 - 1一次合并形成三个小分队西安小分队0、6、7、8以 0 为根6、7、8 的父节点都是 0集合大小为 4所以ufs[0] -4ufs[6] 0ufs[7] 0ufs[8] 0成都小分队1、4、9以 1 为根4、9 的父节点都是 1集合大小为 3所以ufs[1] -3ufs[4] 1ufs[9] 1武汉小分队2、3、5以 2 为根3、5 的父节点都是 2集合大小为 3所以ufs[2] -3ufs[3] 2ufs[5] 2。此时数组状态索引0 1 2 3 4 5 6 7 8 9 ufs-4 -3 -3 2 1 2 0 0 0 1第二次合并西安 成都小分队8 号属于 0 的集合和 1 号属于 1 的集合合并将两个集合合并为一个。此时 0 成为新的根集合大小为 437所以ufs[0] -7ufs[1] 01 的父节点变为 0。最终数组状态索引0 1 2 3 4 5 6 7 8 9 ufs-7 0 -3 2 1 2 0 0 0 1通过这个数组我们能快速获取以下信息查找元素 6 的根ufs[6] 0非负继续查ufs[0] -7负所以根是 0属于大小为 7 的集合判断元素 3 和 7 是否同属一个集合3 的根是 27 的根是 0根不同所以不属于同一个集合统计集合个数数组中负数的个数0 和 2 对应的 - 7、-3共 2 个集合。2.2 核心操作的原理并查集的核心是三个操作查找Find、合并Union、统计集合个数Count其原理如下1查找Find找到元素的根节点查找操作的目标是给定一个元素编号沿着父指针一直向上追溯直到找到根节点数组值为负数的元素。步骤若当前元素的ufs值为负数直接返回该元素根节点若为非负数将当前元素更新为其父节点重复步骤 1直到找到根节点。例如查找元素 9 的根ufs[9] 1非负→ 父节点是 1ufs[1] 0非负→ 父节点是 0ufs[0] -7负→ 根节点是 0返回 0。2合并Union将两个集合合并为一个合并操作的目标是将两个不同集合的根节点连接起来形成一个新的集合。步骤分别找到两个元素的根节点root1和root2若root1 root2两个元素已在同一个集合合并失败返回false若root1 ! root2将较小的集合合并到较大的集合优化策略避免树过深更新根节点的集合大小ufs[root1] ufs[root2]并将较小集合的根节点的父指针指向较大集合的根节点ufs[root2] root1合并成功返回true。为什么要 “小集合合并到大连合”这是为了避免树的高度过高导致后续查找操作变慢。比如如果总是把大连合合并到小集合可能会形成一条长长的链如 1→2→3→...→n查找根节点需要 O (n) 时间而 “小合并到大” 能保证树的高度始终较低查找效率更高。3统计集合个数Count统计当前不相交集合的数量由于根节点的ufs值为负数非根节点为非负数所以只需遍历整个数组统计负数的个数即可。例如初始状态数组有 10 个负数集合个数为 10合并为三个小分队后数组有 3 个负数集合个数为 3合并西安和成都小分队后数组有 2 个负数集合个数为 2。2.3 并查集的优化 —— 路径压缩Find 操作的终极优化在上述基础实现中查找操作的效率取决于树的高度。如果树的高度过高如链式结构查找操作的时间复杂度会退化到 O (n)。为了进一步优化查找效率我们可以引入“路径压缩”技术。路径压缩的原理路径压缩是指在执行查找操作时将查找路径上的所有元素的父指针直接指向根节点。这样一来下次再查找这些元素时就能直接找到根节点大大减少查找次数。举个例子原来的查找路径是 9→1→0根节点执行路径压缩后9 的父指针直接指向 0下次查找 9 时一步就能找到根节点。路径压缩的实现非常简单只需在Find操作中将当前元素的父节点更新为根节点即可可以用递归或迭代实现。优化后的Find操作时间复杂度几乎能达到O (1)均摊时间复杂度。三、并查集的 C 实现 —— 完整代码与详细注释基于上述原理我们用 C 实现一个通用的并查集类包含查找带路径压缩、合并小集合合并到大集合、统计集合个数三个核心操作。3.1 基础实现带路径压缩和按大小合并#include vector #include iostream using namespace std; // 并查集类 class UnionFindSet { public: // 构造函数初始化并查集每个元素自成一个集合值为-1 UnionFindSet(size_t size) : _ufs(size, -1) {} // 查找操作找到元素index的根节点带路径压缩 int FindRoot(int index) { // 边界检查index必须在合法范围内 if (index 0 || index _ufs.size()) { throw invalid_argument(index out of range); } // 迭代实现路径压缩找到根节点后回溯更新路径上所有元素的父节点 int root index; // 第一步找到根节点 while (_ufs[root] 0) { root _ufs[root]; } // 第二步路径压缩将index到root路径上的所有元素直接指向root while (_ufs[index] 0) { int parent _ufs[index]; // 保存当前元素的父节点 _ufs[index] root; // 将当前元素的父节点更新为根节点 index parent; // 继续处理下一个元素 } return root; } // 合并操作将x1和x2所在的集合合并返回是否合并成功 bool Union(int x1, int x2) { // 找到两个元素的根节点 int root1 FindRoot(x1); int root2 FindRoot(x2); // 如果根节点相同说明已经在同一个集合无需合并 if (root1 root2) { return false; } // 按大小合并将较小的集合合并到较大的集合 // _ufs[root]为负数绝对值是集合大小所以比较时用“”因为-3 -4代表大小3 4 if (_ufs[root1] _ufs[root2]) { // root1的集合更小 swap(root1, root2); // 保证root1是较大集合的根 } // 合并更新较大集合的大小将较小集合的根指向较大集合的根 _ufs[root1] _ufs[root2]; // 集合大小相加负数相加 _ufs[root2] root1; // 小集合的根指向大集合的根 return true; } // 统计集合个数数组中负数的个数 size_t Count() const { size_t count 0; for (int e : _ufs) { if (e 0) { count; } } return count; } // 辅助函数打印并查集数组用于调试 void PrintUFS() const { cout 并查集数组状态; for (int e : _ufs) { cout e ; } cout endl; } private: vectorint _ufs; // 父指针数组存储集合关系 }; // 测试代码 int main() { // 初始化10个元素编号0-9 UnionFindSet ufs(10); cout 初始状态 endl; ufs.PrintUFS(); cout 当前集合个数 ufs.Count() endl; // 输出10 // 合并西安小分队0、6、7、8 ufs.Union(0, 6); ufs.Union(0, 7); ufs.Union(0, 8); cout \n合并西安小分队后 endl; ufs.PrintUFS(); cout 当前集合个数 ufs.Count() endl; // 输出810-37不对初始10合并3次减少3个集合10-37 // 合并成都小分队1、4、9 ufs.Union(1, 4); ufs.Union(1, 9); cout \n合并成都小分队后 endl; ufs.PrintUFS(); cout 当前集合个数 ufs.Count() endl; // 输出67-25哦初始10合并069、078、087合并146、195所以是5 // 合并武汉小分队2、3、5 ufs.Union(2, 3); ufs.Union(2, 5); cout \n合并武汉小分队后 endl; ufs.PrintUFS(); cout 当前集合个数 ufs.Count() endl; // 输出35-23 // 合并西安和成都小分队8和1 ufs.Union(8, 1); cout \n合并西安和成都小分队后 endl; ufs.PrintUFS(); cout 当前集合个数 ufs.Count() endl; // 输出23-12 // 查找元素9的根节点 int root9 ufs.FindRoot(9); cout \n元素9的根节点 root9 endl; // 输出0 // 判断元素3和7是否同属一个集合 int root3 ufs.FindRoot(3); int root7 ufs.FindRoot(7); cout 元素3的根节点 root3 endl; // 输出2 cout 元素7的根节点 root7 endl; // 输出0 cout 元素3和7是否同属一个集合 (root3 root7 ? 是 : 否) endl; // 输出否 return 0; }3.2 代码解释构造函数接收集合大小size初始化_ufs数组为size个 - 1每个元素自成一个集合FindRoot 函数迭代实现路径压缩分两步①找到根节点②将路径上所有元素的父指针指向根节点确保下次查找更快Union 函数按集合大小合并将较小集合合并到较大集合避免树过深提高查找效率Count 函数遍历数组统计负数个数即集合个数PrintUFS 函数辅助调试打印当前并查集数组状态。3.3 递归实现路径压缩可选除了迭代实现FindRoot也可以用递归实现路径压缩代码更简洁// 递归实现查找带路径压缩 int FindRootRecursive(int index) { if (index 0 || index _ufs.size()) { throw invalid_argument(index out of range); } // 递归终止条件找到根节点_ufs[index] 0 if (_ufs[index] 0) { return index; } // 路径压缩将当前元素的父节点更新为根节点递归查找 _ufs[index] FindRootRecursive(_ufs[index]); return _ufs[index]; }递归实现的优点是代码简洁但缺点是当集合元素较多、树较深时可能会导致栈溢出递归深度超过系统栈限制。因此实际开发中更推荐使用迭代实现。四、并查集的经典应用场景 —— 面试高频题实战并查集的应用非常广泛尤其在图论、动态连通性问题中。下面我们结合两道 LeetCode 高频面试题讲解并查集的实际应用。4.1 应用一省份数量LeetCode 547题目链接https://leetcode.cn/problems/number-of-provinces/description/题目描述有n个城市其中一些彼此相连另一些没有相连。如果城市a与城市b直接相连且城市b与城市c直接相连那么城市a与城市c间接相连。一个 “省份” 是由一组直接或间接相连的城市组成组内不含其他没有相连的城市。给你一个n x n的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连isConnected[i][j] 0表示不直接相连。返回矩阵中省份的数量。示例输入isConnected [[1,1,0],[1,1,0],[0,0,1]]输出2解释有 2 个省份[0,1] 和 [2]。解题思路这道题本质上是求图的连通分量个数用并查集可以轻松解决初始化并查集每个城市自成一个集合遍历矩阵isConnected如果isConnected[i][j] 1i 和 j 直接相连则合并i和j所在的集合最终并查集中的集合个数就是省份的数量。C 代码实现#include vector using namespace std; class Solution { public: int findCircleNum(vectorvectorint isConnected) { int n isConnected.size(); if (n 0) { return 0; } // 初始化并查集n个城市每个城市初始为-1 vectorint ufs(n, -1); // 查找函数带路径压缩lambda表达式 auto findRoot [ufs](int x) { int root x; // 找到根节点 while (ufs[root] 0) { root ufs[root]; } // 路径压缩 while (ufs[x] 0) { int parent ufs[x]; ufs[x] root; x parent; } return root; }; // 遍历矩阵合并相连的城市 for (int i 0; i n; i) { for (int j i 1; j n; j) { // j从i1开始避免重复合并i和j与j和i是一样的 if (isConnected[i][j] 1) { int root1 findRoot(i); int root2 findRoot(j); if (root1 ! root2) { // 按大小合并 if (ufs[root1] ufs[root2]) { swap(root1, root2); } ufs[root1] ufs[root2]; ufs[root2] root1; } } } } // 统计集合个数省份数量 int count 0; for (int e : ufs) { if (e 0) { count; } } return count; } }; // 测试代码 int main() { vectorvectorint isConnected1 {{1,1,0},{1,1,0},{0,0,1}}; Solution sol; cout 省份数量 sol.findCircleNum(isConnected1) endl; // 输出2 vectorvectorint isConnected2 {{1,0,0},{0,1,0},{0,0,1}}; cout 省份数量 sol.findCircleNum(isConnected2) endl; // 输出3 return 0; }代码优化点遍历矩阵时j从i1开始避免重复处理(i,j)和(j,i)减少合并次数查找函数使用迭代实现路径压缩避免栈溢出合并时按集合大小合并优化树的高度。4.2 应用二等式方程的可满足性LeetCode 990题目链接https://leetcode.cn/problems/satisfiability-of-equality-equations/description/题目描述给定一个由表示变量之间关系的字符串方程组成的数组每个字符串方程equations[i]的长度为 4并采用两种形式之一ab或a!b。在这里a 和 b 是小写字母不一定不同表示单字母变量名。只有当可以为变量分配整数的值使得所有给定的方程都满足时才返回true否则返回false。示例输入1[ab,b!a]输出1false解释1ab和b!a矛盾无法同时满足。输入2[ab,bc,ac]输出2true解释2所有方程都满足。解题思路这道题的核心是“相等关系具有传递性”可以用并查集来处理首先处理所有 “” 方程将相等的变量合并到同一个集合中因为相等关系传递ab 且 bc则 a、b、c 在同一个集合然后处理所有 “!” 方程检查两个变量是否在同一个集合中。如果在则矛盾返回false如果不在则满足条件所有方程处理完毕后返回true。C 代码实现#include vector #include string using namespace std; class Solution { public: bool equationsPossible(vectorstring equations) { // 26个小写字母初始化并查集 vectorint ufs(26, -1); // 查找函数带路径压缩 auto findRoot [ufs](int x) { int root x; while (ufs[root] 0) { root ufs[root]; } // 路径压缩 while (ufs[x] 0) { int parent ufs[x]; ufs[x] root; x parent; } return root; }; // 第一步处理所有方程合并相等的变量 for (const string eq : equations) { if (eq[1] ) { // 是方程 char c1 eq[0]; char c2 eq[3]; int x c1 - a; // 转换为0-25的索引 int y c2 - a; int root1 findRoot(x); int root2 findRoot(y); if (root1 ! root2) { // 按大小合并 if (ufs[root1] ufs[root2]) { swap(root1, root2); } ufs[root1] ufs[root2]; ufs[root2] root1; } } } // 第二步处理所有!方程检查是否矛盾 for (const string eq : equations) { if (eq[1] !) { // 是!方程 char c1 eq[0]; char c2 eq[3]; int x c1 - a; int y c2 - a; int root1 findRoot(x); int root2 findRoot(y); if (root1 root2) { // 两个变量在同一个集合矛盾 return false; } } } // 所有方程都满足 return true; } }; // 测试代码 int main() { vectorstring equations1 {ab,b!a}; Solution sol; cout (sol.equationsPossible(equations1) ? true : false) endl; // 输出false vectorstring equations2 {ab,bc,ac}; cout (sol.equationsPossible(equations2) ? true : false) endl; // 输出true vectorstring equations3 {ab,b!c,ca}; cout (sol.equationsPossible(equations3) ? true : false) endl; // 输出false return 0; }关键思路相等关系是传递的适合用并查集合并不等关系是直接的只需检查两个变量是否在同一个集合即可必须先处理所有 “” 方程再处理 “!” 方程否则会出现逻辑错误比如先处理 “a!b”再处理 “ab”此时无法发现矛盾。4.3 应用三其他常见场景除了上述两道题并查集还有很多经典应用最小生成树Kruskal 算法用并查集判断边的两个顶点是否在同一个集合避免生成环岛屿数量LeetCode 200可以用并查集合并相邻的陆地最终统计集合个数冗余连接LeetCode 684找到导致图中有环的边用并查集判断边的两个顶点是否已连通朋友圈问题与省份数量类似统计社交网络中的连通分量个数。这些问题的核心思想都是“动态连通性”并查集是解决这类问题的最优选择。五、并查集的时间复杂度与空间复杂度分析5.1 时间复杂度并查集的时间复杂度主要取决于查找Find和合并Union操作经过路径压缩和按大小 / 秩合并优化后查找操作的均摊时间复杂度为O (α(n))其中 α 是阿克曼函数的反函数合并操作的时间复杂度由查找操作决定也是O (α(n))统计集合个数的时间复杂度为 O (n)其中 n 是元素个数。阿克曼函数 α(n) 增长极其缓慢在实际应用中α(n) 几乎可以看作是一个常数对于 n 10^60α(n) ≤ 6。因此优化后的并查集可以看作是 “近常数时间” 的数据结构效率极高。5.2 空间复杂度并查集的空间复杂度为O (n)其中 n 是元素个数因为需要一个大小为 n 的数组存储父指针信息。六、并查集的常见误区与注意事项6.1 常见误区忘记边界检查查找或合并时元素索引可能超出数组范围导致数组越界路径压缩实现错误递归实现时未考虑栈溢出迭代实现时未正确更新父指针合并时未按大小 / 秩合并导致树的高度过高查找效率退化处理顺序错误如等式方程问题中先处理 “!” 再处理 “”导致无法发现矛盾根节点判断错误误将非负数当作根节点或负数当作非根节点。6.2 注意事项始终确保元素索引在合法范围内必要时添加边界检查优先使用迭代实现路径压缩避免栈溢出合并时务必按大小或秩合并优化树的高度根据问题逻辑确定正确的处理顺序如先合并后查询牢记父指针数组的规则负数是根节点绝对值是集合大小非负数是父节点索引。总结并查集是一种简单而强大的数据结构核心解决 “动态连通性” 问题通过路径压缩和按大小 / 秩合并优化后效率几乎达到常数级别。它的代码实现简洁应用场景广泛是面试中高频考察的知识点。并查集的魅力在于其简洁的思想和高效的实现掌握它不仅能帮助你轻松应对面试题还能让你在处理实际问题时多一种高效的解决方案。希望本文能带你真正理解并查集让这个强大的数据结构成为你的 “编程利器”如果觉得本文对你有帮助欢迎点赞、收藏、转发也欢迎在评论区交流讨论