|
5 | 5 | import java.util.List; |
6 | 6 | import java.util.Set; |
7 | 7 |
|
8 | | -/** |
9 | | - * 685. Redundant Connection II |
10 | | - * |
11 | | - * In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are |
12 | | - * descendants of this node, plus every node has exactly one parents, except for the root node which has no parents. |
13 | | - * The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), |
14 | | - * with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed. |
15 | | - * The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that |
16 | | - * represents a directed edge connecting nodes u and v, where u is a parents of child v. |
17 | | - * Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. |
18 | | - * If there are multiple answers, return the answer that occurs last in the given 2D-array. |
19 | | -
|
20 | | - Example 1: |
21 | | - Input: [[1,2], [1,3], [2,3]] |
22 | | - Output: [2,3] |
23 | | - Explanation: The given directed graph will be like this: |
24 | | - 1 |
25 | | - / \ |
26 | | - v v |
27 | | - 2-->3 |
28 | | -
|
29 | | - Example 2: |
30 | | - Input: [[1,2], [2,3], [3,4], [4,1], [1,5]] |
31 | | - Output: [4,1] |
32 | | - Explanation: The given directed graph will be like this: |
33 | | - 5 <- 1 -> 2 |
34 | | - ^ | |
35 | | - | v |
36 | | - 4 <- 3 |
37 | | -
|
38 | | - Note: |
39 | | - The size of the input 2D-array will be between 3 and 1000. |
40 | | - Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array. |
41 | | - */ |
42 | 8 | public class _685 { |
43 | 9 | public static class Solution1 { |
44 | 10 | /** |
@@ -179,7 +145,9 @@ public int[] findRedundantDirectedConnection(int[][] edges) { |
179 | 145 | } |
180 | 146 |
|
181 | 147 | public static class Solution2 { |
182 | | - /**credit: https://discuss.leetcode.com/topic/105108/c-java-union-find-with-explanation-o-n*/ |
| 148 | + /** |
| 149 | + * credit: https://discuss.leetcode.com/topic/105108/c-java-union-find-with-explanation-o-n |
| 150 | + */ |
183 | 151 | public int[] findRedundantDirectedConnection(int[][] edges) { |
184 | 152 | int[] can1 = {-1, -1}; |
185 | 153 | int[] can2 = {-1, -1}; |
|
0 commit comments