本文主要是介绍685. 冗余连接 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
685. 冗余连接 II
- 原题链接:
- 完成情况:
- 解题思路:
- 参考代码:
- 错误经验吸取
原题链接:
685. 冗余连接 II
https://leetcode.cn/problems/redundant-connection-ii/description/
完成情况:
解题思路:
在这里插入代码片
参考代码:
package 代码随想录.并查集;import java.util.ArrayList;public class _685冗余连接II {int N_node = 1002;int fatherPaths [] ;public _685冗余连接II() {fatherPaths = new int[N_node];//并查集初始化for (int i = 0; i < N_node; i++){fatherPaths[i] = i;}}/*** 有向图形成输,然后去除掉节点,存在多个 节点则删除掉最后一个节点* @param edges* @return*/public int[] findRedundantDirectedConnection(int[][] edges) {//这次主要是多了一个方向,构造父亲节点,寻根的时候要考虑方向问题int [] inDegree = new int[N_node]; //记录入度边for (int i = 0;i< edges.length;i++){//入度边inDegree[edges[i][1]] += 1;}//找出入度为 2的节点所对应的边,注意要倒序,因为优先返回最后出现在二维数组中的答案ArrayList<Integer> twoInDegree = new ArrayList<Integer>(); //注意要重点留意那些有多个入度的边,因为如果只有一个节点的话,你删除掉了那个节点,那么就会导致出现单节点,就无法构成一颗树for (int i = edges.length - 1;i>=0;i--){if (inDegree[edges[i][1]] == 2){ //只要大于1条边就记录下来twoInDegree.add(i);}}//处理图中情况1 和情况2//如果有入度为2的节点,那么一定是两条边里删除一个,看看删哪个可以构成树if (!twoInDegree.isEmpty()){if (isTreeAfterRemoveEdge(edges,twoInDegree.get(0))){return edges[twoInDegree.get(0)];}return edges[twoInDegree.get(1)];}//明确没有入度大于2的情况了,那么一定有有向环,找到构成环的边返回就可以了if (!twoInDegree.isEmpty()){if (isTreeAfterRemoveEdge(edges,twoInDegree.get(0))){return edges[twoInDegree.get(0)];}return edges[twoInDegree.get(1)];}//明确没有入度为2的情况,那么 一定有有向环,找到构成环的边返回就可以了return getRemoveEdge(edges);}/*** 在有向图里找到删除的那条边,使其变成树* @param edges* @return 要删除的边*/private int[] getRemoveEdge(int[][] edges) {initFatherPath();for (int i = 0; i < edges.length; i++) {if (sameEdge(edges[i][0], edges[i][1])){ //构成 有向环了,就删除要删除的边return edges[i];}joinEdge(edges[i][0],edges[i][1]);}return null;}/**** @param edgeA* @param edgeB*/private void joinEdge(int edgeA, int edgeB) {edgeA = fatherPaths[edgeA];edgeB = fatherPaths[edgeB];if (edgeA == edgeB) return;fatherPaths[edgeB] = edgeA; // A -> B}/**** @param edgeA* @param edgeB* @return*/private boolean sameEdge(int edgeA, int edgeB) {edgeA = fatherPaths[edgeA];edgeB = fatherPaths[edgeB];return edgeB == edgeA;}/****/private void initFatherPath() {//并查集初始化for (int i =0;i<N_node;++i){fatherPaths[i] = i;}}/*** 删一条边之后判断是不是树* @param edges* @param deleteEdge 要删除的边* @return true: 是树, false: 不是树*/private boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge) {initFatherPath();for (int i = 0; i < edges.length;i++){if (i == deleteEdge) continue;if (sameEdge(edges[i][0],edges[i][1])){ //构成有向环了,一定不是树return false;}joinEdge(edges[i][0],edges[i][1]);}return true;}
}
错误经验吸取
这篇关于685. 冗余连接 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!