网站建设 质量标准汽车营销策划方案ppt

网站建设 质量标准,汽车营销策划方案ppt,大连网站开发哪儿好薇,优秀企业网站设计欣赏这道题也是并查集基础题目。1.并查集可以解决的问题#xff1a;#xff08;1#xff09;判断两个节点是否在一个集合。#xff08;2#xff09;将两个节点添加到一个集合中。2.题目要求#xff1a;对于一个无向图#xff0c;返回一条可以删去的边#xff0c;使得结果图…这道题也是并查集基础题目。1.并查集可以解决的问题1判断两个节点是否在一个集合。2将两个节点添加到一个集合中。2.题目要求对于一个无向图返回一条可以删去的边使得结果图是一个有着N个节点的树即只有一个根节点。如果有多个答案则返回二维数组中最后出现的边。3.思路可以从前向后遍历每一条边因为优先让前面的边连上边的两个节点如果不在同一个集合就加入集合即同一个根节点。1如下图所示节点a和节点b不在同一个集合那么就可以将两个节点连接在一起。2如果边的两个节点已经出现在同一个集合里则说明这条边的两个节点已经连在一起了再加入这条边一定就出现环了如下图所示。4.注意题目已说明该图是在树的基础上添加一条边得到因此只会有一条冗余边因此可以在遇到同一个根的两个节点后直接返回即可。附代码class Solution { private int[] p; public int[] findRedundantConnection(int[][] edges) { int n edges.length; p new int[n]; for(int i 0;i n;i){ p[i] i; } for(int i 0;;i){ //无限循环会一直执行到找到冗余边并返回所以该方法一定有返回值因为树的性质保证了该方法一定有一条冗余边 //若加上i n条件则编译器会认为如果循环内所有if(pa pb)条件都不满足那么循环会正常结束此时循环结束后就没有返回值 //编译器在编译时只做静态代码分析不执行程序逻辑推理 //编译器认为条件判断里的return只是可能返回若加上i n有限循环中还需要在下面加一个return条件 int pa find(edges[i][0] - 1); //因为节点编号从1开始所以要 - 1做数组映射 int pb find(edges[i][1] - 1); if(pa pb){ return edges[i]; } p[pa] pb; } } private int find(int x){ if(p[x] ! x){ p[x] find(p[x]); } return p[x]; } }