Masala #1062

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 30 %

#Depth-First Search

#Union Find

#Graflar nazariyasi

Bekatlar

Bitlandiya mamlakatida n ta bekat bor. Ular mos ravishda koordinatalar sistemasida joylashgan. Bir bekatdan ikkinchisiga borish mumkin bo'ladi qachonki ular bitta vertikal yoki gorizantal chiziqda yotgan bo'lsa. BitVoy ning aniqlashicha shunaqa bekatlar bor ekanki ulardan ba'zi bir bekatlarga borishning imkoni yo'q ekan. Shu sababdan Hokim unga eng kam bekatlar qurish orqali barcha bekatlarni bog'lashni buyurdi. Unga bunda yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida birinchi qatorda \(n(1 \le n \le 100)\) bekatlar soni keyingi n ta qatorda har bir bekat koordinatasi kiritiladi x_i va y_i \((1\le x_{i}, y_{i} \le 1000)\) .

Chiquvchi ma'lumotlar:

Chiqish faylida qurilishi kerak bo'lgan minimal bekatlar sonini kiriting.

Misollar

#	input.txt	output.txt
1	2 2 1 1 2	1
2	2 2 1 4 1	0

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin