Leetcode Problem 685. Redundant Connection II
Leetcode Solutions
Detecting Redundant Connection with Union-Find
- Initialize parent array to keep track of each node's parent.
- Initialize two variables, candA and candB, to store candidate edges if a node has two parents.
- Iterate through the edges: a. If the current node does not have a parent, set its parent. b. If the current node already has a parent, store the current and previous edges as candA and candB.
- Initialize Union-Find structure with each node as its own parent.
- Iterate through the edges again: a. If the current edge was marked with a zero node (indicating a second parent), skip it. b. Perform Union-Find. If a cycle is detected, store the current edge.
- If a cycle is detected and candA is not empty, return candA. Otherwise, return candB or the last edge that created the cycle.
Detecting Redundant Connection with Depth-First Search (DFS)
Ask Question
Programming Language
Purpose:
image/screenshot of info(optional)
Full Screen
Loading...
Suggested Answer
Answer
Full Screen
Copy Answer Code
Loading...