Cerință
Inițial n noduri sunt izolate. Operația 1 u v adaugă o legătură neorientată. Operația 2 u v întreabă dacă există un drum între u și v folosind legăturile adăugate până atunci.
Tip de problemă: Disjoint Set Connectivity.
Date de intrare
n q, apoi q operații.
Date de ieșire
Pentru fiecare întrebare, 1 dacă există drum, altfel 0.
Restricții
1 ≤ n,q ≤ 2000; 1 ≤ u,v ≤ n. Sunt permise legături repetate și u=v. Există cel puțin o întrebare.
Observații
Selecție Algo25 pentru pregătirea interviurilor. Enunț, exemple și soluții originale.
Reper tematic pentru pregătire: https://www.hackerrank.com/interview/interview-preparation-kit
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Ultima întrebare găsește drumul 1 → 2 → 3. Nodul 4 rămâne izolat. O legătură adăugată mai târziu nu schimbă răspunsul unei întrebări anterioare.Mărește schema ↗Date de intrare
4 4
2 1 2
1 1 2
1 2 3
2 1 3
Date de ieșire
0
1
Exemplul 2
Date de intrare
1 1
2 1 1
Date de ieșire
1
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
RÂNDUL TĂU
Editor de codTrimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →
Un pas, apoi următorul.Înapoi sus ↑