Union find algorithm - Julia asked the peer to give a different question to ask - January 8, 2018 - 10:00 PM mock interview
/* | |
In this problem, a tree is an undirected graph that is connected and has no cycles. | |
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), | |
with one additional edge added. The added edge has two different vertices chosen from 1 to N, and | |
was not an edge that already existed. | |
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, | |
that represents an undirected edge connecting nodes u and v. | |
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple | |
answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the | |
same format, with u < v. | |
Example 1: | |
Input: [[1,2], [1,3], [2,3]] | |
Output: [2,3] | |
Explanation: The given undirected graph will be like this: | |
1 | |
/ \ | |
2 - 3 | |
third edge -> | |
Example 2: distinct 5, 5 distinct edge, 4 distinct edge | |
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] | |
Output: [1,4] | |
Explanation: The given undirected graph will be like this: | |
Note: | |
The size of the input 2D-array will be between 3 and 1000. | |
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array. | |
---- Discussion starts from here --- | |
Julia's idea and the discussion with the peer: | |
Determine if there is a cycle. How to determine if there is a cycle? | |
Tree, graph, using depth first search. | |
Union find algorithm - one group | |
The peer asked Julia what is the base case. | |
What is the base case? | |
1 | |
/ \ | |
2 - 3 | |
3 -> 2 -> 1 | |
base case: | |
4 | |
/ \ | |
1 3 | |
/\ | |
5 2 | |
Hint given by the peer: | |
Example 1: Hint given by peer: | |
[1,2] | |
set(1,2) | |
[1,3] | |
set(1,2,3) | |
[2,3] | |
Example 2: | |
set(1), set(2), set(3), set(4), set(5) | |
1. [1,2] | |
set(1, 2) | |
2. [2,3] | |
set(1, 2, 3) | |
3. [3,4] | |
set(1,2,3,4) | |
4. [1,4] | |
It is called union-find merge disjointed groups. | |
5 - 1 - 2 | |
| | | |
4 - 3 | |
[1, 4] in part of cycle | |
detect the cycle | |
5 -> 1 -> 2 -> 3 -> 4 -> 1, there is cycle | |
4 -> 1 -> 5 | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment