Update redundant-connection.py

kamyu104 · web-flow · commit f70dee412a71 · 2017-09-25T21:38:53.000+08:00
diff --git a/Python/redundant-connection.py b/Python/redundant-connection.py
@@ -1,6 +1,34 @@
 # Time:  O(nlog*n) ~= O(n), n is the length of the positions
 # Space: O(n)
 
+# We are given a "tree" in the form of a 2D-array, with distinct values for each node.
+#
+# In the given 2D-array, each element pair [u, v] represents that v is a child of u in the tree.
+#
+# We can remove exactly one redundant pair in this "tree" to make the result a (rooted) tree.
+#
+# You need to find and output such a pair. If there are multiple answers for this question,
+# output the one appearing last in the 2D-array. There is always at least one answer.
+#
+# Example 1:
+# Input: [[1,2], [1,3], [2,3]]
+# Output: [2,3]
+# Explanation: Original tree will be like this:
+#   1
+#  / \
+# 2 - 3
+#
+# Example 2:
+# Input: [[1,2], [1,3], [3,1]]
+# Output: [3,1]
+# Explanation: Original tree will be like this:
+#   1
+#  / \\
+# 2   3
+# Note:
+# The size of the input 2D-array will be between 1 and 1000.
+# Every integer represented in the 2D-array will be between 1 and 2000.
+
 class UnionFind(object):
     def __init__(self, n):
         self.set = range(n)
