代码随想录算法第五十六天| KamaCoder108多余的边、KamaCoder109多余的边Ⅱ

KamaCoder 108 多余的边题目链接108.多余的边文档讲解代码随想录视频讲解多余的边思路与感想这道题目确实挺简单是一道并查集的模板提但说实话我并没有想出来原因是这个多余的边我最开始一直没搞懂什么叫多余的边它的判断标准是啥直到看完卡哥讲解之后才后知后觉原来是每条边相连的两个节点如果说还未建立起这条边的时候这两个节点就可以互相抵达了那么这条边就是多余的。知道这一点题目就很简单了判断两个节点能不能相互抵达就是并查集模板里面的isSame方法然后建立边就是joint方法只需要在遍历每条边建立点与点联系前事先判断这两个点是不是已经在一个集合了如果是那这条边就没必要加了直接输出这条多余的边即可。由于题目是在N个节点N-1条边的树的基础上加了一条多余的边导致边的个数为N那么由此可以知道多余的边只有一条所以输出之后就可以直接return了。收获1.边的重复到底是什么2.熟悉并查集模板// 并查集 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int N sc.nextInt(); Disjoint disjoint new Disjoint(N); for (int i 0; i N; i) { // 遍历所有的边 int u sc.nextInt(); int v sc.nextInt(); if (disjoint.isSame(u, v)) { // 每次遍历一条边都先判断两个节点是否已经在一个集合了是的话说明这条边就是多余的边 System.out.println(u v); return; } disjoint.joint(u, v); // 两个节点尚未在同一个集合那就joint } } } class Disjoint { // 并查集模板 private int[] father; public Disjoint(int N) { father new int[N 1]; for (int i 1; i N 1; i) { father[i] i; } } public int find(int n) { if (father[n] n) { return n; } father[n] find(father[n]); return father[n]; } public boolean isSame(int u, int v) { u find(u); v find(v); return u v; } public void joint(int u, int v) { u find(u); v find(v); if (u v) { return; } father[v] u; } }KamaCoder 109 多余的边 Ⅱ题目链接109.多余的边 Ⅱ文档讲解代码随想录视频讲解多余的边 Ⅱ思路与感想这道题目只想到了前两种入度为2的情况但没有想到isTreeAfterDeleteEdge这个函数的实现逻辑觉得删除两个边再分别判断这个图是不是仍为树的逻辑好麻烦更别提想到把两种情况合并处理的方法了。直到听完了卡哥的讲解才发现这道题是真的难啊。在消化完后进行代码复现时有几个遗漏的地方。第一个是初始化二维集合edges的时候没有edges.add(new ArrayList())这个占位初始化第一维的操作第二个疏漏就是在判断情况3的时候忘记写else里面的join逻辑了。本题可以说是上一题的超级加强版分类讨论情况的数量和代码量直线上升因此感觉收获巨大。收获1.判断图删除一条边后是否为树的核心逻辑就是判断这个图还是不是环2.并查集不能表示方向但仍可以判断图是不是环import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int N sc.nextInt(); ListListInteger edges new ArrayList(); // 存储所有边的情况 int[] indegree new int[N 1]; // 记录每个节点的入度 for (int i 0; i N 1; i) { // 遍历所有边的情况接收到edges中同时记录每个节点入度 if (i 0) { edges.add(new ArrayList()); // 下标0只作占位操作不实质添加 continue; } edges.add(new ArrayList()); int start sc.nextInt(); // 边的起点 int end sc.nextInt(); // 边的终点 edges.get(i).add(start); edges.get(i).add(end); indegree[end]; // 终点节点入度自增 } ListInteger temp new ArrayList(); // 存储含入度等于2节点的边 for (int i 1; i N 1; i) { if (indegree[edges.get(i).get(1)] 2) { temp.add(i); } } Disjoint disjoint new Disjoint(N); // 新建并查集工具类对象 if (temp.size() 0) { // 存在含入度等于2节点的边(情况1 情况2) if (isTreeAfterDeleteEdge(edges, temp.get(1), disjoint)) { // 删除后输入的边仍为树说明删对了输出答案 System.out.println(edges.get(temp.get(1)).get(0) edges.get(temp.get(1)).get(1)); return; } else { // 删了后输入的边图不为树那么真正需要删除的边就是先输入的那条边 System.out.println(edges.get(temp.get(0)).get(0) edges.get(temp.get(0)).get(1)); return; } } for (int i 1; i N 1; i) { // 不存在含入度等于2节点的边(情况3) int u edges.get(i).get(0); int v edges.get(i).get(1); if (disjoint.isSame(u, v)) { // 删除多余的边 System.out.println(u v); return; } else { disjoint.joint(u, v); // 非多余边时就建立两个节点的联系 } } } public static boolean isTreeAfterDeleteEdge(ListListInteger edges, int order, Disjoint disjoint) { // 判断删除某条边后是否仍为树 for (int i 1; i edges.size(); i) { if (i order) { // 遍历到要删除的边就直接continue模拟这条边已经不在了 continue; } int u edges.get(i).get(0); int v edges.get(i).get(1); if (disjoint.isSame(u, v)) { // 删除了目标边之后还是发现了多余的边说明删错了 return false; } else { disjoint.joint(u, v); } } return true; } } class Disjoint { // 并查集模板工具类 private int[] father; public Disjoint(int N) { father new int[N 1]; for (int i 1; i N 1; i) { father[i] i; } } public int find(int n) { if (father[n] n) { return n; } father[n] find(father[n]); return father[n]; } public boolean isSame(int u, int v) { u find(u); v find(v); return u v; } public void joint(int u, int v) { u find(u); v find(v); if (u v) { return; } father[v] u; } }今天第二题比较困难花了三个多小时攻克总共五个多小时左右。上午年级集中会议刷了一早JUC八股。会议结束后去健身房练肩感觉爆炸。下午回寝室就一直刷算法刷到第二题提交报错了困了睡了一个小时醒了吃完晚饭接着刷。明天考数据采集打算写完博客再稍微看会毕竟是开卷感觉没什么好复习的然后接着把没写完的项目继续赶赶进度。