Node Reachability: Directed Paths, Undirected Connectivity, and a Removed Direct Edge

A graph has `n` nodes numbered `0` to `n - 1` and a list `edges`, where each edge `[u, v]` joins nodes `u` and `v`. You are given two distinct nodes, `source` and `target`, and two boolean flags that decide which edges may be used and in which direction. The interview built the problem up in three steps: (1) with the edges read as directed, can `target` be reached from `source`? (2) with the same edges read as undirected, are `source` and `target` connected? (3) if the direct connection between `source` and `target` breaks, is there still another connection between them? This function answers all three: `directed` chooses how the edges are read, and `exclude_direct` applies the third step on top of either reading. **Rules** - When `directed` is `True`, an edge `[u, v]` can be followed only from `u` to `v`. When `directed` is `False`, it can be followed in both directions. - When `exclude_direct` is `True`, an edge that joins `source` and `target` directly (stored as `[source, target]` or as `[target, source]`) is unusable, and every other edge stays usable. If no such edge exists, the flag changes nothing. When `exclude_direct` is `False`, every edge is usable. - Return `True` if some path leads from `source` to `target` using only usable edges, each followed in an allowed direction, and `False` otherwise. - Do not modify `edges`: the caller keeps using the same list after the call. **Function signature** ```python def has_connection(n: int, edges: list[list[int]], source: int, target: int, directed: bool, exclude_direct: bool) -> bool: ``` **Constraints** - `2 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5` - Every edge `[u, v]` has `0 <= u, v < n` and `u != v`. - No edge appears twice, and no pair of nodes is joined in both orders: if `[u, v]` is present, neither another `[u, v]` nor `[v, u]` is. - `0 <= source, target < n` and `source != target`. - All values fit in a 32-bit signed integer; no value can exceed 2^31 - 1, so a 32-bit `int` is enough in every language. **Example 1** ```text Input: n = 4, edges = [[0, 1], [1, 2], [3, 2]], source = 0, target = 3, directed = True, exclude_direct = False Output: False ``` Following the edges' direction, node 0 reaches node 1 and then node 2, but the only edge at node 3 points from 3 to 2, so node 3 cannot be reached. With `directed = False` the same input returns `True`: read as undirected, the edges give the path 0 - 1 - 2 - 3. **Example 2** ```text Input: n = 5, edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]], source = 2, target = 3, directed = False, exclude_direct = True Output: False ``` Without the edge `[2, 3]`, nodes 0, 1 and 2 are connected to each other and nodes 3 and 4 to each other, but nothing joins the two groups. With the same graph and flags, `source = 0` and `target = 1` would return `True`: ignoring `[0, 1]` still leaves the path 0 - 2 - 1.