Minimum Path Node Count with an Optional Broken Vertex

Problem Statement

You are given an undirected graph with n vertices labeled from 0 to n - 1. The graph is represented as an adjacency list connections, where connections[i] is a list of neighbors adjacent to node i.

You are also given three integers: start, target, and broken.

Your task is to find the minimum number of nodes in a path from start to target that does not pass through the broken vertex. The node count includes both the start and target vertices.

Return the minimum number of nodes on such a path. If no valid path exists, or if start or target coincides with broken, return -1.

Function Signature

def min_path_nodes(connections: list[list[int]], start: int, target: int, broken: int) -> int:
    pass

Constraints

• 1 <= connections.length <= 10^5
• 0 <= connections[i][j] < connections.length
• The total number of edges across all adjacency lists does not exceed 2 * 10^5.
• 0 <= start, target, broken < connections.length
• There are no self-loops or duplicate edges in connections[i].

Examples

Example 1

Input: connections = [[1, 2], [0, 3], [0, 3], [1, 2]], start = 0, target = 3, broken = 1
Output: 3
Explanation: 
The available paths from 0 to 3 are [0, 1, 3] and [0, 2, 3].
Since node 1 is broken, we must take the path [0, 2, 3], which contains 3 nodes.

Example 2

Input: connections = [[1], [0]], start = 0, target = 1, broken = 1
Output: -1
Explanation: 
The target node itself is broken, so no valid path can reach it.

Example 3

Input: connections = [[1], [0]], start = 0, target = 0, broken = 1
Output: 1
Explanation: 
The path consists of only node 0 itself, which has 1 node.

Edge Cases

• start == target: If start != broken, the path consists of just the start node, so the answer is 1. If start == broken, the answer is -1.
• start == broken or target == broken: Path cannot begin or end on a broken node, return -1.
• Graph components are disconnected or the only available paths traverse broken: return -1.