看动漫是怎么做视频网站,租外国服务器做的网站要备案吗,中国电子网,网站建设公司应该怎么做推广685. 冗余连接 II
问题描述
在本问题中#xff0c;有根树指满足以下条件的 有向 图。该树只有一个根节点#xff0c;所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点#xff0c;而根节点没有父节点。
输入一个有向图#xff0c;该…685. 冗余连接 II
问题描述
在本问题中有根树指满足以下条件的 有向 图。该树只有一个根节点所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点而根节点没有父节点。
输入一个有向图该图由一个有着 n 个节点节点值不重复从 1 到 n的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]用以表示 有向 图中连接顶点 ui 和顶点 vi 的边其中 ui 是 vi 的一个父节点。
返回一条能删除的边使得剩下的图是有 n 个节点的有根树。若有多个答案返回最后出现在给定二维数组的答案。
示例 1 输入edges [[1,2],[1,3],[2,3]]
输出[2,3]示例 2 输入edges [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出[4,1]提示
n edges.length3 n 1000edges[i].length 21 ui, vi n
解题思路与代码实现
总共有两种情况
存在入度为2的点不满足有向树的要求需要删除一条边使该节点入度为1。如果删了一条判断这个图是一个树那么这条边就是答案同时注意要从后向前遍历因为如果两条边删哪一条都可以成为树就删最后那一条。不存在入度为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];// 根据edges数组计算每个点入度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);}}// 如果有入度为2的节点那么一定是两条边里删一个看删哪个可以构成树if (!twoDegree.isEmpty()) {if (isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {return edges[twoDegree.get(0)];}return edges[twoDegree.get(1)];}// 明确没有入度为2的情况那么一定有有向环找到构成环的边返回就可以了return getRemoveEdge(edges);}
}踩坑点
无
