یک مدار الکتریکی سری موازی نامیده میشود، اگر بتوان آن را با اتصال سری و موازی قطعات به هم بهدست آورد. به دست آوردن مقاومت این مدارها به سادگی امکانپذیر است، در حالی که این کار در مدارهای کلی همیشه ساده نیست.
هر مدار الکتریکی را میتوانیم با گرافی مانند $G$ و دو راس $s$ و $t$از آن به عنوان دو سر مدار مشخص کنیم. در این صورت، گراف سری موازی را میتوان به صورت بازگشتی به این صورت تعریف کرد:
برنامهای بنویسید که از سطر اول فایل ورودی، به ترتیب تعداد رئوس، تعداد یالها و شمارهی رئوس دو سر مدار و از سطرهای بعد لیست یالهای یک گراف را دریافت کرده، مشخص کند که آیا این گراف سری موازی است یا خیر و اگر سری موازی بود مقاومت آن را تعیین کند.
اطلاعات در فایل خروجی به این صورت ذخیره میشود: در سطر اول این فایل، سری موازی بودن مدار را با یکی از پیغامهای Serial-parallel یا Not Serial-parallel مشخص کنید و در سطر دوم فایل، اگر مدار سری موازی بود، عددی حقیقی بنویسید که نشاندهندهی مقاومت مدار است.
فرض کنید که تعداد رئوس و تعداد یالهای گراف به ترتیب از ۵۰ و ۵۰۰ بیشتر نیست. به مثال زیر توجه کنید. مدار ورودی این مثال در شکل زیر نشان داده شده است.
ورودي نمونه | خروجي نمونه |
---|---|
10 11 1 4 $ \quad$ –> 7 6 1 2 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 7 8 2 3 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 6 5 3 4 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 8 9 4 5 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 9 10 1 8 $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$ 10 5 –> | Is serial-parallel 0.66 |