#1618Hard#24 in D. E. Shaw's list· asked at 2 companies
Remove Max Number of Edges to Keep Graph Fully Traversable
Hosted on LeetCode
Solve it on LeetCode, track it here.
This problem's full statement lives on LeetCode. Open it in a new tab, then come back to mark it solved, add notes and keep your streak.
LeetCode Premium locked?
Most company-tagged LeetCode problems are behind Premium. If you have ChatGPT Plus or Claude Pro, ask it for the full statement, examples and constraints. The buttons below open a chat with the prompt already filled in.
What we know
Example 1
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]] Output: 2
Edges [1,1,2] and [1,1,3] can be removed.
Example 2
Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]] Output: 0
Example 3
Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]] Output: -1
Constraints
- •
1 <= n <= 10^5 - •
1 <= edges.length <= min(10^5, 3 * n * (n - 1) / 2) - •
edges[i].length == 3 - •
1 <= type_i <= 3 - •
All tuples
(type_i, u_i, v_i)are distinct.