سلام
روش کنکوری و سریع برای بدست اوردن مولفه ی همبند قوی وجود داره؟!
مثلاً سوالهایی مثل این سوال پیوست شده رو چطوری میشه بدون اجرای الگوریتم طولانی، حل کرد؟
[attachment=17707]
سلام
راه حل غیر سریع :
تا جایی که من خوندم نه . نکته کنکوری برای این وجود نداره . ولی این راحت حل میشه .
گرافشو شما بکش
خواهی دید که راس F و راس D نمیتونن به عنوان رئوس همبند قوی انتخاب بشن
(( چون F فقط خروجی داره و D فقط ورودی داره ))
و تو همبند قوی باید مسیر رفت و برگشت داشته باشیم .
پس ۱ و ۳ و ۴ میرن
میمونه ۲ . گزینه ۲ صحیحه
راه حل سریع :
بدون کشیدن گرافم میشه فهمید که از هیچ یالی به F مسیر نداریم . همشون ۰ هستن . پس F یکطرفه هستش
D هم به بقیه راس ها همش ۰ هستش پس مسیری به سایر رئوس از D نداریم ( یکطرفه )
ممنون
آره این سوال راحته.
جواب هم که گفتید همون گزینه ۲ هست.
ولی ممکنه سواله دیگه باشه که نشه به این راحتی گزینه هاشو حذف کرد و جواب رو پیدا کرد.
میخواستم ببینم در اون صورت راه حل دیگه ای هم هست یا نه.
(۲۳ دى ۱۳۹۳ ۱۰:۴۱ ب.ظ)Ametrine نوشته شده توسط: ممنون
آره این سوال راحته.
جواب هم که گفتید همون گزینه ۲ هست.
ولی ممکنه سواله دیگه باشه که نشه به این راحتی گزینه هاشو حذف کرد و جواب رو پیدا کرد.
میخواستم ببینم در اون صورت راه حل دیگه ای هم هست یا نه.
انشالله که نمیشه . ولی نکته کنکوری ندیدم من برای این
تو آزمون ها هم عین همینه
مثلا یک نمونشو براتون پیوست کردم که تو آزمون ۱۰۰ درصد اول پارسه دادن
[attachment=17710]
تشکر
اینجا گزینه ۳ جوابه؟
(۲۳ دى ۱۳۹۳ ۱۱:۲۵ ب.ظ)Ametrine نوشته شده توسط: تشکر
اینجا گزینه ۳ جوابه؟
نه
گزینه ۴ جوابه
تا یه جایی درست رفتی
ببین اینجا {C,F,E} همبند قوی هستش . و {A,E.D}
ولی چون این ها هر دوشون عنصر مشترک دارن با هم ادغام میشن و میشه a,c,d,e,f,g
و b هم که تنهاس
یعنی گزینه ۴
شما فقط ادغام نکردی اینه دو تا رو
(۲۳ دى ۱۳۹۳ ۱۱:۴۳ ب.ظ)ardaaalan نوشته شده توسط: نهالان g چرا اومد اینجا؟
گزینه ۴ جوابه
تا یه جایی درست رفتی
ببین اینجا {C,F,E} همبند قوی هستش . و {A,E.D}
ولی چون این ها هر دوشون عنصر مشترک دارن با هم ادغام میشن و میشه a,c,d,e,f,g
و b هم که تنهاس
یعنی گزینه ۴
شما فقط ادغام نکردی اینه دو تا رو
تو هیچ کدوم نبود که
شرمنده بادم رفت
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
(۲۳ دى ۱۳۹۳ ۱۱:۵۴ ب.ظ)ardaaalan نوشته شده توسط: شرمنده بادم رفتمنم این مسیر رو دیدم ولی گفتم شاید سوال اینو نمیخواد دیگه!
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
پس وقتی بین همبندها اشتراک بود باید با هم ادغام بشن.
ممنون
(۲۳ دى ۱۳۹۳ ۱۱:۵۸ ب.ظ)Ametrine نوشته شده توسط:(23 دى ۱۳۹۳ ۱۱:۵۴ ب.ظ)ardaaalan نوشته شده توسط: شرمنده بادم رفتمنم این مسیر رو دیدم ولی گفتم شاید سوال اینو نمیخواد دیگه!
شما یک مسیر d,g,f,c,e رو یادتون رفته در نظر بگیرین
منم یادم رفت
چون مسیر دو طرفس . یعنی هم از d به e مسیر دارین و هم از e به d
حالا این ۳ تا با هم عنصر مشترک دارن . پس با هم ادغام میشن
و حاصل ادغام میشه a,c,d,e,f,g
پس وقتی بین همبندها اشتراک بود باید با هم ادغام بشن.
ممنون
بله . خواهش میکنم
یه چیزی تو مایه های کلید خارجیه اون عنصر e