2021能看的网站免费的知乎亚马逊官网中国网页版

2021能看的网站免费的知乎,亚马逊官网中国网页版,东莞网站建设都找菲凡网络,现在的网站一般做多宽最好并查集理论基础 一、核心思想 高效处理动态连通性问题。 并查集用于判断两个元素是否在同一个集合中。它将每个集合看作一棵树#xff0c;集合的“代表”就是这棵树的根节点。如果两个元素的根节点相同#xff0c;它们就在同一个集合。 二、三大核心操作 初始化 功能集合的“代表”就是这棵树的根节点。如果两个元素的根节点相同它们就在同一个集合。二、三大核心操作初始化功能开始时每个元素都是一个独立的集合其根节点是自己。代码void init(int n) { for (int i 0; i n; i) { father[i] i; // 每个节点的父节点都是自己 } }寻根功能找到指定元素所在集合的根节点。这是并查集的灵魂。优化路径压缩在寻找根的过程中将路径上的所有节点直接指向根节点极大提升后续查询效率。代码int find(int u) { // 如果u的父节点不是自己就递归寻找并把u的父节点直接设置为根 return u father[u] ? u : father[u] find(father[u]); }合并功能将两个元素所在的集合合并成一个。核心原则必须先找到两个元素的根节点再将其中一个根节点连接到另一个上。代码void join(int u, int v) { u find(u); // 找到u的根 v find(v); // 找到v的根 if (u v) return; // 如果根相同说明已在同一集合无需操作 father[v] u; // 将v的根连接到u的根上 }判断功能判断两个元素是否在同一个集合。代码bool isSame(int u, int v) { return find(u) find(v); }三、常见误区join函数的正确写法错误写法void join(int u, int v) { if (isSame(u, v)) return; // 虽然判断对了但... father[v] u; // ...这里连接的是原始节点u和v而不是它们的根 }问题这样会破坏树的结构导致后续find操作出错。例如join(1, 2); join(3, 2);后isSame(1, 3)会返回false不符合预期。正确写法void join(int u, int v) { u find(u); // 必须先找根 v find(v); // 必须先找根 if (u v) return; father[v] u; // 连接的是根节点 }原因保证了总是将两个集合的根进行连接维护了数据结构的正确性。四、另一个优化按秩合并思想在合并时总是将“秩”可以理解为树的高度或大小较小的树挂载到较大的树上避免树的高度过快增长。虽然理论上很好但路径压缩的优化效果已经非常出色且代码更简洁。在实际应用和面试中通常只使用路径压缩就足够了。五、完整代码模板int n 1005; // n根据题目中节点数量而定一般比节点数量大一点就好 vectorint father vectorint (n, 0); // 并查集初始化 void init() { for (int i 0; i n; i) { father[i] i; } } // 并查集里寻根的过程 int find(int u) { return u father[u] ? u : father[u] find(father[u]); // 路径压缩 } // 判断 u 和 v是否找到同一个根 bool isSame(int u, int v) { u find(u); v find(v); return u v; } // 将v-u 这条边加入并查集 void join(int u, int v) { u find(u); // 寻找u的根 v find(v); // 寻找v的根 if (u v) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回 father[v] u; }六、复杂度分析空间复杂度O(n)需要一个father数组。时间复杂度接近 O(1)。路径压缩后的并查集时间复杂度在O(logn)与O(1)之间且随着查询或者合并操作的增加时间复杂度会越来越趋于O(1)。路径压缩保证了每次操作后树的结构都趋向于扁平化使得后续的查询和合并操作非常快。KamaCoder107.寻找存在的路线107. 寻找存在的路线1.思路本题是并查集的模板题掌握基础模板就能直接拿下。#include iostream #include vector using namespace std; int n,m; vectorintfather(105,1); void init(){ for(int i1;in;i){ father[i]i; } } int find(int u){ if(ufather[u]) return u; return father[u]find(father[u]); } bool issame(int u,int v){ ufind(u); vfind(v); return uv; } void join(int u,int v){ ufind(u); vfind(v); if(uv) return; father[u]v; } int main(){ cinnm; init(); for(int i0;im;i){ int s,t;cinst; join(s,t); } int source,destination; cinsourcedestination; coutissame(source,destination); return 0; }2.Reference107. 寻找存在的路径 | 代码随想录