آمار پرسش:

• پرسیده شده: 2014-06-03 01:43:25 -0500
• مشاهده شده: 1,101 بار
• بروز شده: 2014-06-03 17:30:42 -0500

پرسش‌های مشابه:

آیا گراف قویا همبند است؟

یافتن کوتاه ترین دور در گراف ساده

کد برای بررسی یک ریختی 2 گراف

جزوه ی برنامه نویسی قسمت (گراف)

پيدا كردن دومين كوتاهترين مسير بين دو راس گراف با توجه به الگوريتم ديكسترا

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

حداکثر تعداد یال‌های گراف بدون مثلث

یافتن کوچکترین پیچ و مهره با مقایسه آنها

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

پیدا کردن مولفه های قویا همبند گراف جهت دار

2

قبلا یک سوال برای این که ببینیم آیا یک گراف قویا همبند هست یا نه پرسیده شده و پاسخ درست هم بهش داده شده: کافی است یک بار روی خود گراف و یک بار پس از برعکس کردن جهت همه یالها، از یک راس مثل $v$ الگوریتم DFS را اجرا کنیم. گراف قویا همبند است اگر و تنها اگر در هر دو گراف کل راسها از $v$ قابل دسترسی باشند.

اما اگر بخواهیم خود مولفه های قویا همبند یک گراف جهت دار رو پیدا کنیم باید چه کنیم؟

الگوریتم گراف مولفه قویا-همبند

2014-06-03 01:43:25 -0500

کلاه قرمزی 3097 ● 21 ● 34 ● 57

پاک‌کردن   ویرایش سوال

نظرات

http://codeforces.com/contest/427/problem/C این سوال به الگوریتم مولفه قویا همبند نیاز داره میتونید برای تمرین حلش کنید

2014-06-03 01:56:54 -0500 سماق

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 09:46:46 -0500 امیر شکری

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-27 08:39:40 -0500 امیر شکری

2

از همان‌چیزی که در ابتدا گفتید استفاده می‌کنیم! این‌جا را ببینید.

همون‌طور که خودتون هم گفتید ابتدا روی گراف DFS زده و هر بار که پیمایش یک راس (شامل فرزندانش) تمام شد، آن‌را در پشته‌ای می‌اندازیم، پس از این‌کار ترتیبی از راس‌ها داریم.

حال بر روی گراف معکوس DFS می‌زنیم. ولی از راسی شروع می‌کنیم که بالای پشته است. و هر بار آن راس و راس‌هایی که به آن می‌رسد را از پشته خارج می‌کنیمِ این راس‌ها یک مولفه‌ی قویا همبند هستند و دوباره از راس بالای پشته شروع می‌کنیم و این الگوریتم را تا جایی ادامه می‌دهیم که پشته خالی شود.

2014-06-03 01:52:41 -0500

یوسفی 631 ● 2 ● 15

پاک‌کردن   ویرایش پاسخ

نظرات

سپاس، فقط یک نکته ظریف وجود داشت:‌ راسها زمانی وارد پشته میشن که کار پیمایش اونها (و فرزندانشون) به اتمام برسه. پاسخ رو اصلاح کردم.

2014-06-03 17:31:36 -0500 کلاه قرمزی

آقا یه بار میتونین یه حرکت شبیه topological sort بزنین تا راس هارو بریزین تو پشته! بعد dfs

2015-07-24 09:56:16 -0500 هویج