- محدودیت زمان: ۴ ثانیه
- محدودیت حافظه: ۱۰۲۴ مگابایت
یک گراف اصلی و یک گراف الگو به شما داده می‌شود. حال شما می‌بایست تعداد زیر گراف‌های موجود در گراف اصلی را پیدا کنید به طوری که این زیرگراف‌ها مشابه گراف الگو باشند. (برای فهم بهتر مسئله به شکل‌های پایین صفحه مراجعه کنید)
نکات مهم:
- گراف‌ها رنگی و جهت‌دار هستند.
- گراف الگو ضعیفا همبند است. (در صورتی که جهت یال‌ها را در نظر نگیریم، گراف ما همبند است)
- بین هر دو راس گراف الگو حداکثر یک یال در هر جهت وجود دارد.
- هر راس گراف شامل یک شناسه یکتا و یک رنگ است.
- هر یال گراف شامل یک شناسه راس مبدا و یک شناسه راس مقصد است.
توجه کنید که سوال راه‌حل کامل ندارد و تست‌ها به صورت رندوم ساخته شدند و برنامه شما هر چه بهتر باشد می‌تواند نمره بهتری دریافت کند.
ورودی
اطلاعات گراف اصلی
- در خط اول ورودی $n_1$ (تعداد راس‌های گراف اصلی) وارد می‌شود.
- سپس در $n_1$ خط بعدی یک رشته (شناسه راس) و $a_i$ (شماره رنگ راس) برای راس‌های گراف اصلی با یک فاصله از هم وارد می‌شوند.
- سپس مقدار $m_1$ (تعداد یال‌های گراف اصلی) وارد می‌شود.
- سپس در $m_1$ خط بعدی دو رشته برای شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف اصلی با یک فاصله از هم وارد می‌شوند.
اطلاعات گراف الگو
- در خط بعد $n_2$ (تعداد راس‌های گراف الگو) وارد می‌شود.
- سپس در $n_2$ خط بعدی یک رشته (شناسه راس) و $b_i$ (شماره رنگ راس) برای راس‌های گراف الگو با یک فاصله از هم وارد می‌شوند.
- سپس مقدار $m_2$ (تعداد یال‌های گراف الگو) وارد می‌شود.
- سپس در $m_2$ خط بعدی دو رشته‌ی شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف الگو با یک فاصله از هم وارد می‌شوند. $$1 \le n_1 \le 30\ 000$$ $$1 \le a_i \le 4$$ $$1 \le m_1 \le 10*n_1$$ $$1 \le n_2 \le 5$$ $$1 \le b_i \le 4$$ $$1 \le m_2 \le 20$$
خروجی
خروجی تنها شامل یک عدد است که تعداد زیرگراف‌های موجود از گراف اصلی (شبیه به گراف الگو) را نشان می‌دهد.
مثال
ورودی نمونه ۱
5
1 1
2 2
3 2
4 2
5 2
8
1 2
1 5
2 3
2 4
2 5
3 4
5 3
5 4
3
A 1
B 2
C 2
2
A B
B C
خروجی نمونه ۱
5
توضیحات نمونه‌ی ۱
گراف اصلی نمونه ۱:
گراف الگو نمونه ۱:
با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۵ تاست، بنابراین عدد ۵ در خروجی چاپ می‌شود.
| راس A | راس B | راس C | |
|---|---|---|---|
| زیرگراف ۱ | راس ۱ | راس ۲ | راس ۳ |
| زیرگراف ۲ | راس ۱ | راس ۲ | راس ۴ |
| زیرگراف ۳ | راس ۱ | راس ۲ | راس ۵ |
| زیرگراف ۴ | راس ۱ | راس ۵ | راس ۳ |
| زیرگراف ۵ | راس ۱ | راس ۵ | راس ۴ |
ورودی نمونه ۲
5
1 1
2 2
3 2
4 2
5 2
4
1 2
1 3
1 4
1 5
3
A 1
B 2
C 2
2
A B
A C
خروجی نمونه ۲
12
توضیحات نمونه‌ی ۲
گراف اصلی نمونه ۲:
گراف الگو نمونه ۲:
با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۱۲ تاست، بنابراین عدد ۱۲ در خروجی چاپ می‌شود.
| راس A | راس B | راس C | |
|---|---|---|---|
| زیرگراف ۱ | راس ۱ | راس ۲ | راس ۳ |
| زیرگراف ۲ | راس ۱ | راس ۲ | راس ۴ |
| زیرگراف ۳ | راس ۱ | راس ۲ | راس ۵ |
| زیرگراف ۴ | راس ۱ | راس ۳ | راس ۲ |
| زیرگراف ۵ | راس ۱ | راس ۳ | راس ۴ |
| زیرگراف ۶ | راس ۱ | راس ۳ | راس ۵ |
| زیرگراف ۷ | راس ۱ | راس ۴ | راس ۲ |
| زیرگراف ۸ | راس ۱ | راس ۴ | راس ۳ |
| زیرگراف ۹ | راس ۱ | راس ۴ | راس ۵ |
| زیرگراف ۱۰ | راس ۱ | راس ۵ | راس ۲ |
| زیرگراف ۱۱ | راس ۱ | راس ۵ | راس ۳ |
| زیرگراف ۱۲ | راس ۱ | راس ۵ | راس ۴ |
ورودی نمونه ۳
2
1 1
2 1
2
1 2
2 1
2
A 1
B 1
1
A B
خروجی نمونه ۳
2
توضیحات نمونه‌ی ۳
گراف اصلی نمونه ۳:
گراف الگو نمونه ۳:
با توجه به جدول زیر تعداد زیرگراف‌های مشابه گراف الگو در گراف اصلی، ۲ تاست، بنابراین عدد ۲ در خروجی چاپ می‌شود.
| راس A | راس B | |
|---|---|---|
| زیرگراف ۱ | راس ۱ | راس ۲ |
| زیرگراف ۲ | راس ۲ | راس ۱ |
ارسال پاسخ برای این سؤال