leetcode684冗余连接(模板题,理解背过就行)
考了图的连通,笔试碰见了还好老底没忘,不然就尬住了,总结一下。
一、题目
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵
n
个节点 (节点值1~n
) 的树中添加一条边后的图。添加的边的两个顶点包含在1
到n
中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为n
的二维数组edges
,edges[i] = [ai, bi]
表示图中在ai
和bi
之间存在一条边。请找出一条可以删去的边,删除后可使得剩余部分是一个有着
n
个节点的树。如果有多个答案,则返回数组edges
中最后出现的那个。
二、示例
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
三、提示
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges中无重复元素
给定的图是连通的
四、详解
package main;
/**
* @author 芊嵛
* @date 2024/3/22
*/
public class Test02 {
public static void main(String[] args) {
// 节点n
int n = 5;
// 边
int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
// 调用函数求结果
System.out.print("[" + res(edges)[0] + "," + res(edges)[1] + "]");
}
public static int[] res(int[][] edges) {
// 定义连通的图,为的是下标从1开始所以+1
int[] map = new int[edges.length + 1];
// 初始化自己给自己连通,自己到自己肯定是通的
for (int i = 0; i < map.length; i++) {
map[i] = i;
}
// 全部遍历看是否连通
for (int i = 0; i < edges.length; i++) {
// 如果连通代表不需要这个点可以删,多了就成环了
if (connected(edges[i][0], edges[i][1], map)) {
return new int[]{edges[i][0], edges[i][1]};
} else {
// 如果不连通把他们加入图中
union(edges[i][0], edges[i][1], map);
}
}
// 返回值在此题中无用
return new int[0];
}
// 找到根节点
public static int find(int n, int[] map) {
while (map[n] != n) {
map[n] = map[map[n]];
n = map[n];
}
return map[n];
}
// 根据根节点判断是否连通
public static boolean connected(int n, int m, int[] map) {
// 如果两个点连通代表他们的根节点都相同
return find(n, map) == find(m, map);
}
// 如果不连通,让他们加入图中
public static void union(int n, int m, int[] map) {
int f1 = find(n, map);
int f2 = find(m, map);
if (f1 == f2) {
return;
}
map[f1] = f2;
}
}
五、拓展
标签:map,连通,int,节点,edges,冗余,leetcode684,public,模板 From: https://www.cnblogs.com/qy-blog/p/18091700可以在试着求一下连通分量