卖游戏币网站制作,源码网站制作教程,今题网免费发布信息网,网站建设平台方案684.冗余连接 题目#xff1a;树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1#xff5e;n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间#xff0c;且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 …684.冗余连接 题目树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges edges[i] [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 请找出一条可以删去的边删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案则返回数组 edges 中最后出现的那个。 题目链接684.冗余连接 代码如下 修改join函数
class Solution {public int[] father;public int[] findRedundantConnection(int[][] edges) {//构造并查集 过程中两个边根一样则删除int nedges.length;fathernew int[n1];//初始化for(int i1;in;i){father[i]i;}int[] resultnull;boolean flag;for(int j0;jedges.length;j){flagjoin(edges[j][0],edges[j][1]);if(flagtrue){return new int[]{edges[j][0],edges[j][1]};}}return result;}public int find(int u){if(ufather[u]) return u;else return find(father[u]);}boolean join(int u, int v) {u find(u); // 寻找u的根v find(v); // 寻找v的根if (u v) return true;father[v] u;return false;}
}685. 冗余连接 II 再分析 题目 在本问题中有根树指满足以下条件的 有向 图。该树只有一个根节点所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点而根节点没有父节点。 输入一个有向图该图由一个有着 n 个节点节点值不重复从 1 到 n的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]用以表示 有向 图中连接顶点 ui 和顶点 vi 的边其中 ui 是 vi 的一个父节点。 返回一条能删除的边使得剩下的图是有 n 个节点的有根树。若有多个答案返回最后出现在给定二维数组的答案 题目链接 685. 冗余连接 II 解题思路 先判断入度 删除入度为2的边的一条 判断删除后是不是树即可 再使用并查集判断是否有环是否有冲突 此时的冲突一定是构成环 如何使用并查集判断删除后是不是树 因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根那么这条边添加上之后 这个图一定不是树了 如何使用并查集判断判断是否有环有环时 附加的边指向根节点 附加的边指向根节点而且是在环路中的最后一条被访问到的边 class Solution {private static final int N 1010; // 如题二维数组大小的在3到1000范围内private int[] father;public Solution() {father new int[N];// 并查集初始化for (int i 0; i N; i) {father[i] i;}}// 并查集里寻根的过程private int find(int u) {if(u father[u]) {return u;}father[u] find(father[u]);return father[u];}// 将v-u 这条边加入并查集private void join(int u, int v) {u find(u);v find(v);if (u v) return ;father[v] u;}// 判断 u 和 v是否找到同一个根本题用不上private Boolean same(int u, int v) {u find(u);v find(v);return u v;}/*** 初始化并查集*/private void initFather() {// 并查集初始化for (int i 0; i N; i) {father[i] i;}}/*** 在有向图里找到删除的那条边使其变成树* param edges* return 要删除的边*/private int[] getRemoveEdge(int[][] edges) {initFather();for(int i 0; i edges.length; i) {if(same(edges[i][0], edges[i][1])) { // 构成有向环了就是要删除的边return edges[i];}join(edges[i][0], edges[i][1]);}return null;}/*** 删一条边之后判断是不是树* param edges* param deleteEdge 要删除的边* return true: 是树 false 不是树*/private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge){initFather();for(int i 0; i edges.length; i){if(i deleteEdge) continue;if(same(edges[i][0], edges[i][1])) { // 构成有向环了一定不是树return false;}join(edges[i][0], edges[i][1]);}return true;}public int[] findRedundantDirectedConnection(int[][] edges) {int[] inDegree new int[N];for(int i 0; i edges.length; i){// 入度inDegree[ edges[i][1] ] 1;}// 找入度为2的节点所对应的边注意要倒序因为优先返回最后出现在二维数组中的答案ArrayListInteger twoDegree new ArrayListInteger();for(int i edges.length - 1; i 0; i--){if(inDegree[edges[i][1]] 2) {twoDegree.add(i);}}// 处理图中情况1 和 情况2// 如果有入度为2的节点那么一定是两条边里删一个看删哪个可以构成树if(!twoDegree.isEmpty()){if(isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {return edges[ twoDegree.get(0)];}return edges[ twoDegree.get(1)];}// 明确没有入度为2的情况那么一定有有向环找到构成环的边返回就可以了return getRemoveEdge(edges);}
}
