LeetCode题解——冗余连接(并查集)——java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode题解——冗余连接(并查集)——java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2641字，纯文字阅读大概需要4分钟。
内容图文
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
示例 1：
示例 1： 输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / 2 - 3
示例 2：
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:
输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。
解题思路：
使用并查集，比较一边的两个节点的根节点是否相等，如果相等说明能构成闭环，否则没问题
并查集的思想：把当前值A作为下标值去数组中递归查找，如果查到的值正好等于当前值A，说明该节点是根节点，是最老大哥，如果2个节点查到的根节点不不相等，那就合并，任大哥，任意一个作为大哥都可以，具体代码实现如下：
package com.yang.test;
import java.util.Arrays;
/**
* @date 2021/1/1320:32
*/
public class Solution {
public static void main(String[] arg0){
int[][] edges = new int[][]{{1,2},{2,3},{3,4},{1,4},{2,4},{1,3}};
Solution solution = new Solution();
int[] target = solution.findRedundantConnection(edges);
for (int i : target) {
System.out.println(i);
}
// System.out.println(Arrays.asList(target));
}
public int[] findRedundantConnection(int[][] edges) {
int maxValue = 0;//从edges中找最大值，用来创建并查集数组
for (int i = 0; i < edges.length; i++) {
int a = edges[i][0];
int b = edges[i][1];
maxValue = Math.max(Math.max(a, b),maxValue);
}
int parents[] = new int[maxValue+1];
//为根节点赋值，默认每个下标值的根都是他自己，起初都是自成一派
for (int i = 1; i <= maxValue; i++) {
parents[i] = i;
}
int i = 0;//用来表示有多个冗余时，在targets存放的位置，依次++
int[][] targets = new int[maxValue+1][2];
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
int pa = find(a, parents);
int pb = find(b, parents);
if(pa == pb) {
targets[i] = edge;
i++;
}else {
//如果a、b两个的根节点不是同一个，就让他们父类认大哥，随便认，谁当大哥都行
parents[pa] = pb;
}
}
//有多个冗余时，取targets里的最后一次冗余
return targets[i-1];
}
/**
* 并查集查找 parents里每个下标对应的值是他的父类，如果父类和他相等，说明他就是大哥
* @author yang yajun
* @date 2021/1/13 20:49
* @Description: TODO
*/
private int find(int a, int[] parents) {
if (a == parents[a]) {//如果下标值存的是他自己，就是大哥
return a;
}else{
return find(parents[a], parents);
//这句话可以减少查询次数，将a的根节点直接放在a的位置，下次再查就不用依次递归
// return parents[a] = find(parents[a], parents);
}
}
}
内容总结
以上是互联网集市为您收集整理的LeetCode题解——冗余连接(并查集)——java实现全部内容，希望文章能够帮你解决LeetCode题解——冗余连接(并查集)——java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。