参考内容：图论——并查集(详细版)并查集（Disjoint-set）是一种精巧的树形数据结构，它主要用于处理一些不相交集合的合并及查询问题。一些常见用途，比如求联通子图、求最小生成树的Kruskal算法和求最近公共祖先（LCA）等。并查集的理念是只关注个体属于哪个阵营，并不关心这个阵营中个体内部的关系，比如我们常说的张三是李家沟的，王二是王家坝的。同时并查集借助个体代表集体的思想，用一个元素代表整个群体，就像我们开学都会有学生代表、教师代表讲话一样，在台上讲话的那一个学生就代表了学校所有的学生。并查集基本操作并查集的基本操作主要有初始化init、查询find和合并union操作。初始化在使用并
[算法日志]图论：深度优先搜索(DFS)深度优先概论深度优先搜索算法是一种遍历图这种数据结构的算法策略，其中心思想是朝图节点的一个方向不断跳转，当该节点无下一个节点或所有方向都遍历完时，便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。DFS的代码框架voiddfs(参数){if(终止条件){储存结果;return;}for(遍历节点的各个分支){处理节点；dfs(参数);//调用本函数撤销处理，回溯；}}正因为和回溯法有相似之处，所以其在代码结构上与回溯大致相同。深搜三部曲确认递归函数及其参数在深搜过程中，我们通常会定义两个数组容器，一个二维数组储存结果，一个一
代码随想录图论第二天|695.岛屿的最大面积1020.飞地的数量一、695.岛屿的最大面积题目链接：https://leetcode.cn/problems/max-area-of-island/思路：典型的遍历模板题，我采用深度优先，每块岛屿递归遍历的时候计数，递归完比较大小记录最大值。classSolution{intmax=0,k=0;publicintmaxAreaOfIsland(int[][]grid){for(inti=0;igrid.length;i++){for(intj=0;jgrid[0].length;j++){if(grid[i][j]==1){dfs(grid,i,
DFSDFS的结果就是一颗搜索树，只不过每次只记录眼前的分支,然后通过栈回溯到上一个节点再往下朝另一个方向搜索，绘出所有轨迹就是一棵搜索树。排列数字问题#includeusingnamespacestd;constintN=8;intn,path[N];boolst[N];voiddfs(intu){if(u==n){for(inti=0;i>n;dfs(0);return0;}经典N皇后问题#include#include#includeusingnamespacestd;constintN=15;intn;vector>g(N,vector(N,'.'));boolrow[N],col[N
417m.太平洋大西洋水流问题题目链接代码随想录文章讲解链接方法一：用时：1h0m58s思路直接找哪些点既可以到达太平洋又可以到达大西洋比较麻烦，换个角度，找到太平洋可以逆流而上到达的点，再找到大西洋可以逆流而上到达的点，两者的交集就是所需要的答案。用两个二维数组分别记录太平洋和大西洋可以逆流而上达到的点，对边界的点使用DFS。时间复杂度：O(m⋅n)O(m\cdotn)O(m⋅n)。空间复杂度：O(m⋅n)O(m\cdotn)O(m⋅n)。C++代码classSolution{private:intm;intn;voiddfs(vectorvectorint>>&heights,vector
1.数理逻辑2.集合论3.代数系统4.图论图：点+边+边与点的映射函数连通性与判别欧拉图与哈密尔顿图二分图和平面图与欧拉公式树及生成树单源点最短路径：Dijkstra算法对偶图4.图论4.1图的基本概念4.1.1图一个图G是一个三重组V(G),E(G),ΦG>V(G)是一个非空的结点集合E(G)是边的集合关联函数ΦG\Phi_GΦG：是从边集E与结点偶对间的映射函数4.1.2图的分类按边类型分类有向图：每一条边都是有向边有向边（弧）：边对应的偶对是有序的，用序偶对a,b>表示有向边的端点：弧的始点与终点无向图：图中的每一条边都是无向的无向边（棱）：偶对无序，用偶对(a,b)(a,b)(a,
图的代数表示及特征用邻接矩阵或关联矩阵表示图，称为图的代数表示。邻接矩阵设n阶标定图G=(V,E)，V={v1,v2,…,vn}，则G的邻接矩阵是一个n×n矩阵A(G)=[aij](简记为A)，其中若vi与vj邻接，则aij=1，否则aij=0.若aij取为连接vi与vj的边的数目，则称A为推广的邻接矩阵。邻接矩阵的性质邻接矩阵是一个对称方阵。简单标定图的邻接矩阵的各行（列）元素之和是该行（列）对应的点的度。（非简单标定图不成立，有自环的不成立）。若A1和A2是对应于同一个图的两种不同的标定的邻接矩阵，则A1和A2相似，即存在一个可逆矩阵P使得A1=P-1A2P。G是连通的，当且仅当没有G的点
代码随想录图论并查集第七天|685.冗余连接II一、685.冗余连接II题目链接：https://leetcode.cn/problems/redundant-connection-ii/思路：684.冗余连接中是连通且无环的无向图可直接使用并查集模板，如果想判断集合中是否有环，且那条边构成环，只需要每次加入并查集之前先判断一下是否有相同的根，有即构成环。本题是有向图，如果不是树，有两种情况一种是入度为2，如[1,2]、[1,3]、[2,3]。3的入度为2删掉一条边即为树。另一种是无入度为2的点，本身来说，本题原集合不是树，如果无入度为2那么就一定构成环了，如[1,2]、[2,3]、[3,1]
1.最短路径问题1.1带权图的最短路径最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径，其中路径的长度由边的权重确定。常见的最短路径算法包括：Dijkstra算法：适用于解决单源最短路径问题，即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶点来逐步扩展最短路径树，直到找到所有顶点的最短路径。Bellman-Ford算法：适用于解决带有负权边的图的单源最短路径问题。该算法通过对图中所有边进行松弛操作，反复迭代更新每个顶点的最短距离估计，直到收敛并得到最终的最短路径。Floyd-Warshall算法：适用于解决图中所有顶点之间的最短路径问题，即多源最
代码随想录图论第五天|841.钥匙和房间一、841.钥匙和房间题目链接：https://leetcode.cn/problems/keys-and-rooms/思路：钥匙就是索引，遍历过就标记，每拿到一个房间的钥匙，直接for循环递归遍历，深度优先直接拿下。classSolution{publicbooleancanVisitAllRooms(ListListInteger>>rooms){boolean[]visited=newboolean[rooms.size()];dfs(visited,rooms,0);for(booleanb:visited){if(b==false)return
