المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۰:سوال ۳

Trees

گراف همبند $G$ به ما داده شده است. می‌دانیم هیچ $2$ دور از این گراف دارای یال مشترک نیستند. یال‌های گراف $G$ را به تعدادی درخت $T_1$ تا $T_k$ افراز کرده‌ایم (رئوس هر کدام از $T_i$ها زیر مجموعه‌ای از رئوس $G$ هستند). شما باید با حذف کم‌ترین تعداد از این درخت‌ها از گراف $G$ کاری کنید که گراف حاصل دور نداشته باشد.

ورودی

  • ورودی با ۲ عدد صحیح به صورت $N \ M$ شروع خواهد شد. $N$ تعداد راس‌ها و $M$ تعداد یال‌های گراف می‌باشد.
  • در هر یک از $M$ خط بعدی سه عدد طبیعی به صورت $u_i v_i t_i$ آمده است که $u_i$ و $v_i$ بیانگر راس‌های دو سر یال و $t_i$ شماره درختی است که این یال (در افراز گراف به درخت‌ها) به آن تعلق دارد.
  • درخت‌ها از $1$ تا $k$ شماره‌گذاری شده‌اند.
  • $1 \leq N \leq 10000$
  • $N-1 \leq M \leq (3×(N-1))/2$
  • $1 \leq k \leq 10000$

خروجی

در خروجی یک عدد صحیح که بیانگر حداقل تعداد درخت‌هایی که باید حذف شوند است را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
6 6
1 5 1‎
1 2 2‎
2 4 2‎
2 6 3‎
3 4 1‎
3 5 1‎
1

ابزار صفحه