建设收费网站,沈阳做企业网站的,视频解析网站怎么做,上海云盾为网站做防护java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 并查集 并查集
解题思路#xff1a;时间复杂度O( n ∗ l o g 2…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 并查集 并查集
解题思路时间复杂度O( n ∗ l o g 2 n n*log_2n n∗log2n)空间复杂度O( n n n) 并查集是图论的经典算法主要用于处理不相交集合的合并问题常用于求连通子图求最小生成树的Kruskal算法和求最近公共祖先LCA等等其代码操作非常简单初始化init查询find合并union 初始化操作用一个数组parent来存储每个顶点的祖先初始时将自己设置为自己的祖先 查询操作找到i的祖先index是否是祖先的条件为parent[index] index.入果不满足就需要找到index的祖先x并更新parent[index] x 合并操作将两个集合index1和index2合并直接找到两个集合的祖先x和y让x指向y 根据题目描述一棵树中边的数量比结点数量少1但是现在加了一条边让这颗树的边和结点数量一致了树是连通无环的无向图但是多了一条边就会出现环。也就是说这道题的本质上就是让我们求出导致环出现的这条边导致两个顶点属于同一连通分量的边使用并查集每个集合代表一个连通分量初始每个结点都属于不同连通分量。遍历每一条边连接的两个顶点 两个顶点属于不同连通分量说明遍历到当前边之前两个顶点不连通因此当前边不会导致环的出现则合并两个顶点的连通分量两个顶点属于相同连通分量说明在遍历到当前边之前两个顶点已经连通间接而这条边又将两个顶点直接连通从而导致环的出现则它就是罪魁祸首。 代码 class Solution {public int[] findRedundantConnection(int[][] edges) {int n edges.length;//顶点个数int[] parent new int[n 1];//并查集中下标从1开始for (int i 1; i n; i) {parent[i] i;}//遍历每个顶点的边的信息for (int i 0; i n; i) {int[] edge edges[i];//获取顶点i的边int node1 edge[0], node2 edge[1];//获取两条边相邻的顶点if (find(parent, node1) ! find(parent, node2)) {//如果和顶点i都不属于同一个集合连通分量union(parent, node1, node2);//说明这条边不会导致环的出现将两个顶点加入并查集} else {//如果属于同一个集合说明人家两个顶点已经间接连接一起了现在你这条边居然又把我俩直接连接了起来return edge;//此边是构成环的罪魁祸首将其返回}}return new int[0];//无结果返回空}//并查集代码合并public void union(int[] parent, int index1, int index2) {//合并index1和index2的步骤为找到index1的祖先然后找到index2的祖先//让index1的祖先指向index2的祖先完成两个集合的合并。parent[find(parent, index1)] find(parent, index2);}//从parent中查找index的祖先public int find(int[] parent, int index) {if (parent[index] ! index) {//如果index不是自己指向自己说明它自己不是集合中的根节点祖先他也有自己的祖先parent[index] find(parent, parent[index]);//不断找到其祖先然后将其祖先记录到parent[index]位置保证parent[index]只要find一次就必须指向index的祖先}return parent[index];//返回自己的祖先}
}
