1073. One-Stroke Drawing
A pen plotter draws a figure made of n junctions, numbered 0 to n-1, joined by straight or curved segments. Each entry edges[i] = [u, v] is one segment between junctions u and v. Several segments may join the same two junctions, and a segment may start and end at the same junction (a small loop).
Once the pen touches the paper it may not be lifted, and no segment may be drawn twice. The pen may start at any junction and finish at any junction. Return true if the whole figure can be drawn this way, and false otherwise.
Junctions that no segment touches are ignored, and a figure without any segment can trivially be drawn.
Example 1
- Input:
- n = 5, edges = [[0,1],[1,2],[2,0],[2,3]]
- Output:
- true
- Explanation:
Only junctions 2 and 3 have an odd number of segments: start at 3, go to 2, run round the triangle back to 2; junction 4 is ignored.
Example 2
- Input:
- n = 4, edges = [[0,1],[0,2],[0,3]]
- Output:
- false
- Explanation:
All four junctions have an odd number of segments, but a stroke can have at most two odd ends, so it is impossible.
Example 3
- Input:
- n = 6, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3]]
- Output:
- false
- Explanation:
Every junction has an even count, but the two triangles are separate, so the pen would have to be lifted.
Constraints
1 ≤ n ≤ 105
0 ≤ edges.length ≤ 105
edges[i].length == 2
0 ≤ edges[i][j] < n
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n)