Connectivity Under Edge Removals

GoldShow difficultyβetaAdapted from a reddit post

10000ms500MBNov 14, 2026

You are given an integer n, a list edges, and a list queries. There are n nodes labeled from 0 to n - 1. Each element in edges contains [u, v] meaning there is an undirected edge between nodes u and v. Edge i is the element at index i of edges. Two edges can join the same pair of nodes, and they are still separate edges.

Go through queries in order. Each element in queries has one of two forms:

[0, i, 0] removes edge i. A removed edge never comes back.
[1, a, b] asks whether nodes a and b are connected at that moment, meaning some path joins them using only edges that have not been removed yet. A node is always connected to itself.

Return a list with one entry for each query of the form [1, a, b], in the order those queries appear. The entry is 1 if a and b are connected at that moment, and 0 otherwise.

If no query has the form [1, a, b], return an empty list.

You can assume each edge is removed at most once.

Examples

Example 1

Input:  n       = 4
        edges   = [[0, 1],
                   [1, 2],
                   [2, 3]]
        queries = [[1, 0, 3],
                   [0, 1, 0],
                   [1, 0, 3],
                   [1, 2, 3],
                   [1, 0, 1]]
Output: [1, 0, 1, 1]
Explanation: At first the path 0, 1, 2, 3 joins nodes 0 and 3, so the first answer is 1.
Then edge 1, which is [1,2], is removed. That leaves two groups: {0, 1} and {2, 3}.
Nodes 0 and 3 are now in different groups, so the answer is 0.
Nodes 2 and 3 are still joined by edge 2, and nodes 0 and 1 by edge 0, so both answers are 1.

Example 2

Input:  n       = 3
        edges   = [[0, 1],
                   [0, 1],
                   [1, 2]]
        queries = [[0, 0, 0],
                   [1, 0, 1],
                   [0, 1, 0],
                   [1, 0, 1],
                   [1, 2, 2]]
Output: [1, 0, 1]
Explanation: Edges 0 and 1 both join nodes 0 and 1.
After edge 0 is removed, edge 1 still joins them, so the first answer is 1.
After edge 1 is removed too, no edge touches node 0, so the second answer is 0.
Node 2 is always connected to itself, so the last answer is 1.

Example 3

Input:  n       = 5
        edges   = [[0, 1],
                   [1, 2],
                   [2, 0],
                   [3, 4]]
        queries = [[1, 0, 2],
                   [0, 2, 0],
                   [1, 0, 2],
                   [1, 0, 3],
                   [0, 0, 0],
                   [1, 1, 2],
                   [1, 0, 2]]
Output: [1, 1, 0, 1, 0]
Explanation: Nodes 0, 1 and 2 form a cycle, so nodes 0 and 2 are connected.
After edge 2, which is [2,0], is removed, the path 0, 1, 2 still joins them, so the answer is still 1.
No edge ever joins node 3 to nodes 0, 1 or 2, so the third answer is 0.
After edge 0, which is [0,1], is removed, edge 1 still joins nodes 1 and 2, so the answer is 1.
Node 0 now has no edges left, so it is not connected to node 2, and the last answer is 0.

Constraints

$1 \leq$ n $\leq 5 \times 10^4$
$0 \leq$ edges.length $\leq 5 \times 10^4$
edges[i].length $= 2$
$0 \leq$ edges[i][0], edges[i][1] $\leq$ n - 1
edges[i][0] $\neq$ edges[i][1]
$1 \leq$ queries.length $\leq 5 \times 10^4$
queries[j].length $= 3$ , and queries[j][0] is 0 or 1
If queries[j][0] is 0: $0 \leq$ queries[j][1] $<$ edges.length and queries[j][2] $= 0$
If queries[j][0] is 1: $0 \leq$ queries[j][1], queries[j][2] $\leq$ n - 1
Each edge index appears in at most one query of the form [0, i, 0]

Loading editor...

Samples 3

Custom 0

sample

Include in Run

n =integer

edges =int[][]

queries =int[][]

Expected

[1, 0, 1, 1]

Examples

Example 1

Input: n = 4 edges = [[0, 1], [1, 2], [2, 3]] queries = [[1, 0, 3], [0, 1, 0], [1, 0, 3], [1, 2, 3], [1, 0, 1]] Output: [1, 0, 1, 1] Explanation: At first the path 0, 1, 2, 3 joins nodes 0 and 3, so the first answer is 1. Then edge 1, which is [1,2], is removed. That leaves two groups: {0, 1} and {2, 3}. Nodes 0 and 3 are now in different groups, so the answer is 0. Nodes 2 and 3 are still joined by edge 2, and nodes 0 and 1 by edge 0, so both answers are 1.

Example 2

Input: n = 3 edges = [[0, 1], [0, 1], [1, 2]] queries = [[0, 0, 0], [1, 0, 1], [0, 1, 0], [1, 0, 1], [1, 2, 2]] Output: [1, 0, 1] Explanation: Edges 0 and 1 both join nodes 0 and 1. After edge 0 is removed, edge 1 still joins them, so the first answer is 1. After edge 1 is removed too, no edge touches node 0, so the second answer is 0. Node 2 is always connected to itself, so the last answer is 1.

Example 3

Input: n = 5 edges = [[0, 1], [1, 2], [2, 0], [3, 4]] queries = [[1, 0, 2], [0, 2, 0], [1, 0, 2], [1, 0, 3], [0, 0, 0], [1, 1, 2], [1, 0, 2]] Output: [1, 1, 0, 1, 0] Explanation: Nodes 0, 1 and 2 form a cycle, so nodes 0 and 2 are connected. After edge 2, which is [2,0], is removed, the path 0, 1, 2 still joins them, so the answer is still 1. No edge ever joins node 3 to nodes 0, 1 or 2, so the third answer is 0. After edge 0, which is [0,1], is removed, edge 1 still joins nodes 1 and 2, so the answer is 1. Node 0 now has no edges left, so it is not connected to node 2, and the last answer is 0.