Determine Safe Bomb Defusal

Problem Statement

You are tasked with designing a safety monitor for a bomb defusal system. The system consists of a set of states, where each state is represented by an integer from 0 to n-1. From any given state, there are transitions to other states based on input codes. You are currently in state 0 and need to reach a specific target state.

However, some states are 'unstable'. If you enter an unstable state, the bomb will detonate. Additionally, there are 'restricted' transitions that can only be taken if a specific sequence of previous states has been met, but for this simplified model, we consider a state unsafe if it is part of a cycle that does not contain the target or if it leads exclusively to detonation.

Given n (number of states), edges (a list of pairs [u, v] representing a directed transition from u to v), unstable (a list of integers representing states that cause detonation), and target (the goal state), return True if it is possible to reach the target from 0 without passing through any unstable states. Otherwise, return False.

Function Signature

def can_defuse(n: int, edges: list[list[int]], unstable: list[int], target: int) -> bool:

Constraints

• 2 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• 0 is never in unstable.
• target is never in unstable.

Examples

Example 1: Input: n=4, edges=[[0,1], [1,2], [2,3]], unstable=[1], target=3 Output: False Explanation: State 1 is unstable. Since we must pass through 1 to reach 3, it is impossible.

Example 2: Input: n=5, edges=[[0,1], [0,2], [2,3], [2,4]], unstable=[1], target=4 Output: True Explanation: We can take the path 0 -> 2 -> 4, avoiding state 1.