day52 代码随想录算法训练营 图论专题6

1 今日打卡

多余的边 108. 多余的边

多余的边Ⅱ 109. 多余的边II

2 多余的边

2.1 思路

读取边的总数n；
初始化并查集（容量n+1，适配顶点编号从 1 开始的场景）；
逐个读取每条边的两个顶点：
若顶点已连通 → 这条边是「环的关键边」，输出并退出；
若未连通 → 合并两个顶点的集合，继续处理下一条边。

2.2 实现代码

import java.util.*; /** * 主类：利用并查集（Disjoint Set Union）查找无向图中首次出现的环边 * 核心逻辑：遍历每条边，若边的两个顶点已连通（属于同一集合），则该边会形成环，输出并终止程序 */ public class Main { /** * 并查集（Disjoint Set）实现类 * 功能：管理元素的分组，支持查找根节点、合并集合、判断是否同属一个集合 */ static class disJoint { // 父节点数组：father[i] 表示节点i的父节点，用于维护集合关系 private int[] father; /** * 并查集初始化 * @param n 节点总数（数组容量） */ public disJoint(int n) { father = new int[n]; // 初始状态：每个节点的父节点是自己，即每个节点自成一个独立集合 for (int i = 0; i < n; i++) { father[i] = i; } } /** * 查找节点a的根节点（带路径压缩优化） * 路径压缩：将查找路径上的所有节点直接指向根节点，降低后续查找的时间复杂度 * @param a 要查找的节点 * @return 节点a的根节点 */ public int find(int a) { // 递归终止条件：节点a的父节点是自己（a就是根节点） if (a == father[a]) { return a; } // 路径压缩：将a的父节点更新为根节点 father[a] = find(father[a]); // 返回根节点 return father[a]; } /** * 合并两个节点a和b所在的集合 * @param a 节点a * @param b 节点b */ public void join(int a, int b) { // 先找到a和b的根节点（只有根节点能代表集合） int rootA = find(a); int rootB = find(b); // 如果根节点相同，说明已在同一集合，无需合并 if (rootA == rootB) { return; } // 合并：将b集合的根节点挂到a集合的根节点下（也可反过来，不影响核心逻辑） father[rootB] = rootA; } /** * 判断两个节点是否属于同一个集合（是否连通） * @param a 节点a * @param b 节点b * @return true=同集合/连通，false=不同集合/不连通 */ public boolean isSame(int a, int b) { // 根节点相同则属于同一集合 return find(a) == find(b); } } /** * 主方法：程序入口，处理输入、调用并查集、检测环边 * @param args 命令行参数（无实际使用） */ public static void main(String[] args) { // 创建Scanner对象，用于读取控制台输入 Scanner sc = new Scanner(System.in); // 读取边的总数n（后续会遍历n条边） int n = sc.nextInt(); // 初始化并查集：节点编号通常从1开始，所以容量设为n+1（避免下标越界） disJoint dj = new disJoint(n + 1); // 遍历每一条边，逐个检测是否形成环 for (int i = 0; i < n; i++) { // 读取当前边的两个顶点：from（起点）、des（终点） int from = sc.nextInt(); int des = sc.nextInt(); // 检测：两个顶点是否已连通（属于同一集合） if (dj.isSame(from, des)) { // 已连通 → 这条边会形成环，输出该边并终止程序 System.out.println(from + " " + des); return; } else { // 未连通 → 合并两个顶点所在的集合，继续处理下一条边 dj.join(from, des); } } // 关闭Scanner，释放资源 sc.close(); } }

3 多余的边Ⅱ

3.1 思路

核心问题是：给定一个有 n 个节点、n 条边的有向图（本应是一棵有根树 + 1 条冗余边），找出这条冗余边，删除后图能恢复为合法的有根树。
关键背景：有根树的合法条件
每个节点入度为 1（除根节点入度为 0）；
无环；
所有节点连通。
冗余边的两种核心场景（可能叠加）
场景 1：存在入度为 2 的节点 → 冗余边一定是指向该节点的两条边之一；
场景 2：所有节点入度为 1，但图成环 → 冗余边是环中的任意一条（和无向图冗余连接逻辑一致）。
解题核心步骤
遍历所有边，统计每个节点的入度，找到入度为 2 的节点（记为 doubleIn）；
若存在入度为 2 的节点：
收集指向该节点的两条候选边；
先尝试删除后出现的那条候选边，检查剩余边是否能构成合法树（无环 + 连通）；
若删除后合法，这条边就是答案；否则删除另一条候选边；
若不存在入度为 2 的节点：
直接用并查集找环，环中最后出现的那条边就是答案（和无向图冗余连接逻辑一致）。

3.2 实现代码

import java.util.*; /** * 冗余连接II：解决有向图中冗余边问题（入度为2 或 成环） * 核心逻辑： * 1. 先找入度为2的节点，处理其两条候选边 * 2. 若无入度为2的节点，直接找环中的边 */ public class Main { /** * 并查集模板：用于判断连通性、检测环 */ static class Disjoint { // 父节点数组：father[i]表示节点i的父节点 private final int[] father; // 初始化并查集：每个节点的父节点是自己 public Disjoint(int n) { father = new int[n]; for (int i = 0; i < n; i++) { father[i] = i; } } // 合并两个节点所在的集合 public void join(int n, int m) { // 先找到两个节点的根节点 int rootN = find(n); int rootM = find(m); // 根节点相同，无需合并 if (rootN == rootM) return; // 合并：将n的根节点挂到m的根节点下（方向不影响核心逻辑） father[rootN] = rootM; } // 查找节点的根节点（带路径压缩，优化效率） public int find(int n) { // 递归终止：节点的父节点是自己（根节点） // 路径压缩：将当前节点直接指向根节点 return father[n] == n ? n : (father[n] = find(father[n])); } // 判断两个节点是否属于同一集合（是否连通） public boolean isSame(int n, int m) { return find(n) == find(m); } } /** * 边的封装类：存储边的起点(s)和终点(t) */ static class Edge { int s; // 起点 int t; // 终点 public Edge(int s, int t) { this.s = s; this.t = t; } } /** * 节点的封装类：存储节点id、入度(in)、出度(out)（出度本题未用到） */ static class Node { int id; // 节点编号 int in; // 入度 int out; // 出度 } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 输入边的数量（节点数 = 边数 = n） int n = scanner.nextInt(); // 存储所有边 List<Edge> edges = new ArrayList<>(); // 节点映射数组：索引为节点编号（1~n），存储节点的入度/出度信息 Node[] nodeMap = new Node[n + 1]; // 初始化每个节点（节点编号从1开始） for (int i = 1; i <= n; i++) { nodeMap[i] = new Node(); nodeMap[i].id = i; // 初始化节点id } // 记录入度为2的节点编号（初始为null，表示无） Integer doubleIn = null; // 遍历所有边，统计入度，找入度为2的节点 for (int i = 0; i < n; i++) { int s = scanner.nextInt(); // 边的起点 int t = scanner.nextInt(); // 边的终点 // 终点t的入度+1 nodeMap[t].in++; // 若t的入度≥2，标记为入度为2的节点 if (nodeMap[t].in >= 2) { doubleIn = t; } // 将当前边加入边列表 edges.add(new Edge(s, t)); } Edge result = null; // 最终要删除的冗余边 // 场景1：存在入度为2的节点 if (doubleIn != null) { // 收集指向doubleIn的两条候选边 List<Edge> doubleInEdges = new ArrayList<>(); for (Edge edge : edges) { if (edge.t == doubleIn) { doubleInEdges.add(edge); // 找到两条后停止遍历 if (doubleInEdges.size() == 2) break; } } // 候选边1：先出现的边；候选边2：后出现的边 Edge edge1 = doubleInEdges.get(0); Edge edge2 = doubleInEdges.get(1); // 先尝试删除后出现的边edge2，检查剩余边是否能构成合法树 if (isTreeWithExclude(edges, edge2, nodeMap)) { result = edge2; // 删除edge2后合法，edge2是冗余边 } else { result = edge1; // 删除edge2后仍有环，edge1是冗余边 } } else { // 场景2：无入度为2的节点，直接找环中的冗余边 result = getRemoveEdge(edges, nodeMap); } // 输出冗余边的起点和终点 System.out.println(result.s + " " + result.t); scanner.close(); } /** * 验证：删除指定边后，剩余边是否能构成合法树（无环 + 连通） * @param edges 所有边列表 * @param excludeEdge 要排除（删除）的边 * @param nodeMap 节点映射数组 * @return true=合法树，false=仍有环/不连通 */ public static boolean isTreeWithExclude(List<Edge> edges, Edge excludeEdge, Node[] nodeMap) { // 初始化并查集（容量=节点数+1，适配节点编号1~n） Disjoint disjoint = new Disjoint(nodeMap.length + 1); for (Edge edge : edges) { // 跳过要排除的边 if (edge == excludeEdge) continue; // 若当前边的起点和终点已连通，说明剩余边仍有环→不是合法树 if (disjoint.isSame(edge.s, edge.t)) { return false; } // 合并起点和终点的集合 disjoint.join(edge.s, edge.t); } // 遍历完所有边无环，说明是合法树 return true; } /** * 无入度为2的节点时，找环中的冗余边（和无向图冗余连接逻辑一致） * @param edges 所有边列表 * @param nodeMap 节点映射数组 * @return 环中最后出现的那条边 */ public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) { int length = nodeMap.length; // 初始化并查集 Disjoint disjoint = new Disjoint(length); // 遍历所有边，找第一个导致环的边（最后出现的环边） for (Edge edge : edges) { // 若起点和终点已连通，当前边就是环的冗余边 if (disjoint.isSame(edge.s, edge.t)) { return edge; } // 合并起点和终点的集合 disjoint.join(edge.s, edge.t); } // 理论上不会走到这里（题目保证有冗余边） return null; } }