Practice arena
C++17·2 s·128 MB
GraphsIntermediate
Dynamic connectivity
Process union and connectivity operations on n vertices. U a b joins two sets; Q a b asks whether they are connected.
Input
- — The first line contains T.
- — Each case starts with n and q, followed by q operations: U a b or Q a b.
Output
For every Q operation, print YES or NO on its own line.
Technique
path compression + union by size
Target
near-constant amortized
Constraints & sample
- 1 ≤ n, q ≤ 200,000
- 0 ≤ a, b < n
Sample input
1 5 6 Q 0 1 U 0 1 Q 0 1 U 1 2 Q 0 2 Q 3 4
Expected output
NO YES YES NO
Before you submit
- Test the smallest valid input and one awkward edge case.
- Keep the solution within near-constant amortized.
- Match spacing and line breaks exactly before checking 12 hidden cases.
Draft saved locally · 778 / 30,000
Ln 1, Col 1Spaces: 4UTF-8LFC++17
Visible testcases
Editable and stored only in this browser. Hidden judge cases never change.
Checking your session…
Run checks Sample · Submit checks 12 hidden cases
Run the sample first, then send your solution through 12 hidden cases.
Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.