پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
یافتن کوتاه ترین دور در گراف ساده
جزوه ی برنامه نویسی قسمت (گراف)
پيدا كردن دومين كوتاهترين مسير بين دو راس گراف با توجه به الگوريتم ديكسترا
ثابت کنید تعداد درخت هایی که دو راس دارند که اختلاف جمع فاصله هایشان دقیقا 1 است فرد است
پیدا کردن گراف دوبخشی کامل یکرنگ
فکر می کنم که این خیلی معروفه.یه درخت داریم که تو ورودی داده می شه.بعد به هر راس یه عدد اختصاص می دیم که فاصله ی دورترین راس از اونه.حالا بین عدد های اختصاص یافته به راس ها مینیمم رو پیدا کنید.
واسه ی این مثال جواب می شه 2.چون راس 3 از دورترین راس نسبت به خودش 2 تا فاصله داره.
این هم از کد خودم که اصلن بهینه نیست .
الان خودش گفته 3 و یکی این که تو درختی که بیش از 2 راس داره هیچوقت یک راس اویزون مرکز درخت نمی شه... پس کلا 1 منتفی
2015-06-27 11:17:22 -0600 محمد خداداداول قطر رو پیدا می کنی بعد روی مسیر قطر راس مرکز پیدا میشه اگه داده هات زیر 1000 تاشایدم کم تر باشه می شه بیش تر نه چون اول باید فاصله هر دو راس اویزون رو پیدا کنی بعد ماکسیمم رو بگیری که میشه قطرت تو یه ارایه مسیرشو بریزی بعد راس وسطش یا یکی از دو راس وسط مرکز می شه...
2015-06-27 11:21:36 -0600 محمد خدادادتوی هر درخت یا یک راس این ویژگی رو داره یا دو راس مجاور. (اثباتش با خودتون)
.
راه حل اول: $\impliedby$ (O(n
الگوریتم:
۱)در درخت فعلی تمام برگ ها رو حذف کن.
۲) اگر کمتر از ۳ راس باقی مانده بود به ۴ برو.
۳) به ۱ برو.
۴) (راس/رئوس) باقی مانده جواب مسئله هستند.
$\impliedby$ لینک کد
راه حل دوم: $\impliedby$ (O(n
الگوریتم :
۱) از راسی دلخواه Dfs اجرا رو اجرا کن و روی هر راس فاصله آن راس تا راس انتخاب شده رو بنویس.
۲) راسی که بیشترین عدد روی آن نوشته شده را a1 بنام.
راس a1 حتما یکی از دو سر قطر گراف است. (اثباتش با خودتون)
۳) از راس Dfs , a1 اجرا رو اجرا کن و روی هر راس فاصله آن راس تا راس a1 رو بنویس.
4) راسی که بیشترین عدد روی آن نوشته شده را a2 بنام.
رئوس a1 و a2 دو سر قطر گراف هستند. (واضحه چرا)
۵) رئوس قطر گراف رو با ۰ تا m شماره گذاری کن.
۶) درصورتی که m فرد بود رئوس $\lfloor m/2 \rfloor$ و $\lceil m/2 \rceil$ جواب مسئله هستند.
۷) در صورتی که m زوج بود راس $m/2$ جواب مسئله هست.
میشه یه کار قوی تر کرد که به ازای هر راس دورترین راس نسبت بهش رو پیدا کرد. اول با یه DFS واسه هر راس دور ترین راس زیرشو پیدا میکنیم سپس واسه هر راس با توجه به دور ترین راس پدرش میشه دور ترین راس خودشو پیدا کرد $^_^$
دقیقن کار درستی داره می‌کنه :) هیچ مشکلی هم نداره. اگه نمی‌فهمین که چی کار داره می‌کنه مشکل از شماست!
2015-07-01 06:31:27 -0600 احسان@احسان خوب من درست سوال رو متوجه نشده بودم! :) درسته حرف @مرغ تخم یخ سیبیل سیگار :)
2015-07-01 20:19:18 -0600 توفیقیالبته شاید هم درست نباشه، دوباره دارم بهش فکر میکنم مثال نقض میخوره...
2015-07-01 20:23:16 -0600 توفیقیخب گفتم کدشو بزنم و بزارم اینجا که ملت استفاده کنن :) از روش ایمان خان استفاده کردم یعنی این:
۱)در درخت فعلی تمام برگ ها رو حذف کن.
۲) اگر کمتر از ۳ راس باقی مانده بود به ۴ برو.
۳) به ۱ برو.
۴) (راس/رئوس) باقی مانده جواب مسئله هستند.
5)گراف را باز سازی کن و فاصله ی این راس(ها) را تا دور ترین راسشان پیدا کن و به عنوان خروجی بده.
این هم ازلینک کد
