986. Connections Arriving Over Time
There are n machines, numbered 1 to n, and none are connected. Then q
operations arrive in order. Each is either:
1 u v connect machines u and v
2 u v ask whether u and v can currently reach each other
For each question of the second kind, print YES or NO on its own line.
Counting components on a fixed graph is a traversal, and those problems already
exist. This one is different: the edges arrive interleaved with the questions,
so a traversal would have to be re-run per question, which is O(q(n + m)).
A disjoint set answers each question in close to constant time by storing, for each machine, only which group it belongs to.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ u, v ≤ n`
Input
The first line contains two integers n and q.
Each of the next q lines contains three integers: the operation type, then u and v.
Output
For each query of type 2 print YES or NO on its own line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.