Even Cable Counts

Hard

A network has node_count stations numbered from 1 to node_count. Each links[i] = [a, b] is a cable between stations a and b. The network may be split into several separate parts. You may lay at most two new cables, or none at all. A cable cannot run from a station to itself, and you cannot add a second cable between two stations that are already linked. Return True if, after that, every station can end up with an even number of cables, and False otherwise.

Example 1

node_count=5, links=[[1, 2], [2, 3], [3, 4], [4, 5]] → True

Only stations 1 and 5 have an odd number of cables, and they are not linked yet, so one new cable 1–5 is enough.

Example 2

node_count=5, links=[[1, 2], [2, 3], [3, 1], [1, 4]] → True

Stations 1 and 4 are odd, but they are already linked. Station 5 is linked to neither of them, so cables 1–5 and 4–5 fix both.

Example 3

node_count=6, links=[[1, 2], [3, 4], [5, 6]] → False

All six stations are odd, and two new cables can fix at most four of them.

Constraints

3 ≤ node_count ≤ 10⁵
2 ≤ len(links) ≤ 10⁵
links[i] = [a, b], 1 ≤ a, b ≤ node_count, a ≠ b
No two cables join the same pair of stations

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Hash Table

Similar problems

Which Machine to Cure Hard Which Machine to Unplug Hard Most Repeated Colour on a Path Hard Routes Between Equal Peaks Hard Lay a Graph Out on a Grid Hard

Input

node_count=5, links=[[1, 2], [2, 3], [3, 4], [4, 5]]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 84 tests on the server, hidden ones included.