802. حالت های امن نهایی را پیدا کنید

802. حالت های امن نهایی را پیدا کنید

مشکل: واسطه

مباحث: Depth-First Searchبا Breadth-First Searchبا Graphبا Topological Sort

یک نمودار کارگردانی وجود دارد n گره ها با هر گره دارای برچسب 0 به n - 1بشر نمودار توسط a نشان داده شده است 0-شاخص آرایه عدد صحیح 2D graph کجا graph[i] یک آرایه عدد صحیح از گره های مجاور گره است i، به این معنی که لبه ای از گره وجود دارد i به هر گره در graph[i]بشر

یک گره یک است گره پایانی در صورت وجود لبه های خروجی. یک گره یک است گره ایمن اگر هر مسیر ممکن از آن گره شروع شود به a گره پایانی (یا یک گره ایمن دیگر).

بازگشت آرایه ای حاوی همه گره های ایمن از نموداربشر پاسخ باید در آن مرتب شود صعودی سفارش

مثال 1:

• ورودی: نمودار = [[1,2]با[2,3]با[5]با[0]با[5]با[]با[]]
• خروجی: [2,4,5,6]
• توضیح: نمودار داده شده در بالا نشان داده شده است. گره های 5 و 6 گره های ترمینال هستند زیرا هیچ لبه خروجی از هیچ یک از آنها وجود ندارد. هر مسیری که از گره های 2 ، 4 ، 5 و 6 شروع می شود ، همه به گره 5 یا 6 منتهی می شوند.

مثال 2:

• ورودی: نمودار = [[1,2,3,4]با[1,2]با[3,4]با[0,4]با[]]
• خروجی: [4]
• توضیح: فقط گره 4 یک گره ترمینال است و هر مسیری که از گره 4 شروع می شود منجر به گره 4 می شود.

محدودیت ها:

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] در یک نظم کاملاً فزاینده طبقه بندی می شود.
• نمودار ممکن است حاوی حلقه های خود باشد.
• تعداد لبه های موجود در نمودار در محدوده خواهد بود [1, 4 * 104]بشر

راه حل:

ما باید تمام گره های ایمن موجود در نمودار را شناسایی کنیم. این شامل بررسی اینکه آیا از یک گره معین شروع می شود ، هر مسیر در نهایت به یک گره ترمینال یا یک گره ایمن دیگر می رسد. راه حل از جستجوی عمق اول (DFS) برای تشخیص چرخه ها و طبقه بندی گره ها به عنوان ایمن یا ناامن استفاده می کند.

بینش های کلیدی:

1. گره های ترمینال: یک گره بدون لبه های خروجی یک گره ترمینال است.
2. گره های ایمن: اگر از آن گره شروع شود ، همه مسیرها در نهایت به گره های ترمینال یا گره های امن دیگر منجر می شوند.
3. تشخیص چرخه: اگر یک گره بخشی از یک چرخه باشد ، یک گره ایمن نیست زیرا مسیرهای شروع شده از آن منجر به گره های ترمینال نمی شوند.

رویکرد:

• ما از DFS برای کاوش در هر گره استفاده می کنیم و تعیین می کنیم که آیا بخشی از یک چرخه است یا خیر. گره هایی که بخشی از چرخه ها هستند یا منجر به چرخه می شوند ناامن هستند.
• گره هایی که در نهایت منجر به گره های ترمینال یا سایر گره های ایمن می شوند ، ایمن هستند.

ما از a استفاده می کنیم visited آرایه با سه ایالت:

• 0: گره هنوز بازدید نشده است.
• 1: گره در حال حاضر بازدید می شود (یعنی در پشته بازگشت).
• 2: گره کاملاً فرآوری شده و ایمن است.

مراحل:

1. DFS را برای هر گره انجام دهید.
2. برای علامت گذاری گره های ایمن/ناامن از ایالات بازدید شده استفاده کنید.
3. تمام گره هایی را که ایمن هستند جمع کنید.

بیایید این راه حل را در PHP پیاده سازی کنیم: 802. حالت های امن نهایی را پیدا کنید

/**
 * @param Integer[][] $graph
 * @return Integer[]
 */
function eventualSafeNodes($graph) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

توضیح:

1. عملکرد DFS:

   • در dfs عملکرد یک جستجوی عمق اول را بر روی گره انجام می دهد و هنگام شروع کار ، آن را به عنوان “بازدید” (1) علامت گذاری می کند (2) وقتی همه همسایگان آن ایمن هستند.
   • اگر هر یک از همسایگان خود به یک چرخه منتهی شوند (نشان داده شده است dfs($neighbor) == 1) ، گره ناامن است (1).
   • اگر همه همسایگان به گره های ترمینال یا گره های ایمن منجر شوند ، به عنوان ایمن مشخص می شود (2).

2. تابع اصلی:

   • ما از طریق تمام گره ها تکرار می کنیم و از DFS استفاده می کنیم تا بررسی کنیم که هر گره ایمن است یا خیر.
   • همه گره های امن در $safeNodes آرایه و بازگشت.

به عنوان مثال Walkthrough:

مثال 1:

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));

• در این مثال ، گره های 5 و 6 گره های ترمینال هستند (بدون لبه های خروجی).
• گره 4 منجر به گره 5 می شود ، بنابراین نیز ایمن است.
• گره 2 منجر به گره 5 می شود ، بنابراین بی خطر است.
• گره های 1 و 0 در نهایت منجر به چرخه یا گره های ناامن می شوند ، بنابراین آنها بی خطر نیستند.

خروجی:

[2, 4, 5, 6]

مثال 2:

$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));

• در این مثال ، فقط گره 4 یک گره ترمینال است و تمام مسیرها که از گره 4 شروع می شود به گره 4 منجر می شود.
• همه گره های دیگر در نهایت منجر به چرخه یا گره های ناامن می شوند.

خروجی:

[4]

پیچیدگی زمان و فضا:

• پیچیدگی زمانی: o (n + e)، کجا حرف تعداد گره ها است و اشمیه تعداد لبه ها است. ما یک بار از هر گره بازدید می کنیم و هر لبه را یک بار پردازش می کنیم.
• پیچیدگی فضا: o (n) برای visited پشته آرایه و بازگشت.

این راه حل به طور موثری گره های ایمن را با استفاده از DFS تعیین می کند و از برآورده شدن محدودیت های مشکل اطمینان می دهد.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: