762. Shared Rail Lines
Two travellers, Ines and Omar, use a rail network with stations numbered 1 to n. Each entry [type, u, v] in edges is a two-way line between stations u and v. A line of type 1 may only be used by Ines, a line of type 2 only by Omar, and a line of type 3 by both of them.
The operator wants to close as many lines as possible, but afterwards each traveller must still be able to get from any station to any other station using only the lines that traveller may use. Return the largest number of lines that can be closed. If even with every line open one of them cannot reach every station, return -1. Repeated lines and lines from a station to itself may appear.
Example 1
- Input:
- n = 3, edges = [[3,1,2],[3,2,3],[3,1,3],[1,1,2],[2,2,3]]
- Output:
- 3
- Explanation:
The shared lines 1-2 and 2-3 already let both travellers reach every station, so the other three lines can all be closed.
Example 2
- Input:
- n = 3, edges = [[1,1,2],[2,2,3],[3,1,3]]
- Output:
- 0
- Explanation:
Ines needs 1-2 plus the shared 1-3, and Omar needs 2-3 plus the shared 1-3, so no line can be closed.
Example 3
- Input:
- n = 4, edges = [[1,1,2],[3,2,3],[2,3,4]]
- Output:
- -1
- Explanation:
Ines cannot reach station 4 with any line she may use, so the answer is -1.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length ≤ 2 * 105
typeis 1, 2 or 3 and 1 ≤ u, v ≤ n for every[type, u, v]
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 300 msC++ 75 msJava 150 msJavaScript 150 msTypeScript 150 ms
Expected complexity
- Time
- O((n + m) * alpha(n))
- Space
- O(n)