当前位置：首页 > java >正文

代码随想录算法训练营第四十八天

java 2025/8/15 0:46:50

卡码网题目:

108. 冗余的边
109. 冗余的边II

其他:

今日总结
往期打卡

108. 冗余的边

跳转: 108. 冗余的边

学习: 代码随想录公开讲解

问题:

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图，例如如图：
在这里插入图片描述
现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

思路:

题目保证只有一条冗余边,所以直接在join时判断就可以记录到无法加入的那条,然后直接输出即可.

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (n)$

代码:

import java.util.*;
class Main{private static int[] parent;private static int xn,yn;private static int find(int x){return x==parent[x]?x:(x=find(parent[x]));}private static boolean isSamed(int x,int y){int a = find(x);int b = find(y);return a==b;}private static void join(int x,int y){int a = find(x);int b = find(y);if(a==b){xn = x;yn = y;return;}parent[b] = parent[a];}public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();parent = new int[n+1];for(int i=1;i<=n;i++){parent[i] = i;}for(int i=0;i<n;i++){int x = sc.nextInt();int y = sc.nextInt();join(x,y);}System.out.println(xn+" "+yn);}
}

109. 冗余的边II

跳转: 109. 冗余的边II

学习: 代码随想录公开讲解

问题:

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：
在这里插入图片描述
现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

思路:

这题也是一条冗边
但由于是有向边,不能简单的记录那个连接成环的边(因为要保证每个节点只能有一个父级且根节点没有父级)
这题需要记录所有的边,并记录入度,如果有入度为2的节点就不能简单删除,只能对那个入度为2的点的两条入边删除,而且并不是所有删除都合法,如果删除后剩下的节点依然有循环不构成一棵树,就是非法,需额外判断.
如果没有入度为2的点(说明连到了根节点上),则可以在冗余时直接删除即可
题目中说明要最后出现的一条边,所以需要注意去除边是从后到前(双端队列就是尾部开始),验环是从前到后(双端队列就是从头到尾,foreach遍历是从头到尾)

复杂度:

时间复杂度: $O (n)$
空间复杂度: $O (n)$

代码:

import java.util.*;
class Main{private static int[] parent;private static int n;private static void init(){for(int i=1;i<=n;i++){parent[i] = i;}}private static int find(int x){return x==parent[x]?x:(x=find(parent[x]));}private static boolean isSamed(int x,int y){int a = find(x);int b = find(y);return a==b;}private static void join(int x,int y){int a = find(x);int b = find(y);if(a==b) return;parent[b] = parent[a];}public static void main(String[] args){Scanner sc = new Scanner(System.in);Deque<int[]> stack = new LinkedList<>();n = sc.nextInt();int[] inDegree = new int[n+1];parent = new int[n+1];int target = -1;for(int i=0;i<n;i++){int x = sc.nextInt();int y = sc.nextInt();stack.add(new int[]{x,y});inDegree[y]++;if(inDegree[y]==2){target = y;}}if(target!=-1){for(int i=0;i<n;i++){int[] arr = stack.pollLast();if(arr[1]==target&&isTree(stack)){System.out.println(arr[0]+" "+arr[1]);return;}stack.addFirst(arr);}}getRemoveEdge(stack);}private static void getRemoveEdge(Collection<int[]> list) {init();for(int[] arr:list){if(isSamed(arr[0],arr[1])){System.out.println(arr[0]+" "+arr[1]);return;}join(arr[0],arr[1]);}}private static boolean isTree(Collection<int[]> list) {init();for(int[] arr:list){if(isSamed(arr[0],arr[1])) return false;join(arr[0],arr[1]);}return true;}
}