اجتياز الرسم البياني. مكون الاتصال
Problem
تم إعطاء رسم بياني غير مرجح غير موجه. من أجله ، تحتاج إلى إيجاد عدد الرؤوس التي تقع في نفس المكون المتصل برأس معين (عد هذا الرأس).
الإدخال: & nbsp؛ يحتوي السطر الأول من الإدخال على رقمين: N و S (1 & le؛ N & le؛ 100؛ 1 & le؛ S & le؛ N) ، حيث N & ndash؛ عدد رؤوس الرسم البياني ، و S & ndash ؛ نظرا للأعلى. الأسطر N التالية تحتوي على أرقام N لكل منها & ndash؛ مصفوفة تجاور الرسم البياني ، حيث يعني 0 عدم وجود حافة بين الرؤوس ، و 1 & ndash؛ حضورها. مضمون أن هناك دائمًا أصفار على القطر الرئيسي للمصفوفة.
الإخراج: & nbsp؛ طباعة عدد صحيح واحد & ndash؛ العدد المطلوب من القمم.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
3 1
0 1 1
1 0 0
1 0 0
| 3 |