Topological Sort و Union-Find و Dijkstradirected graphs · Kahn · 3-color DFS · DSU · Dijkstra

في الأساسيات اتعلمت BFS و DFS، وفي فصل الـ Grid طبّقتهم على جزر وبرتقان بايظ. كل ده كان سؤال واحد: مين يوصل لمين، وفي كام خطوة. دلوقتي هنجاوب على تلات أسئلة أصعب: ترتّب حاجات ليها شروط إزاي، تعرف مين مع مين والـ edges بتيجي واحد واحد، وأقصر طريق لما كل edge ليه وزن.

قبله: Graphs على Grid و Heap بيمهّد لـ: Backtracking و Greedy

هتطلع من الفصل ده وإنت عارف

  • يعني إيه directed graph و in-degree و cycle، وليه الـ cycle في مسائل الترتيب معناها "مستحيل".
  • ترتّب مهام ليها شروط بـ Kahn's algorithm، وتكتشف الـ cycle بالـ DFS أبو تلات ألوان.
  • تبني Union-Find من الصفر، وتفهم path compression و union by size بيعملوا إيه بالظبط.
  • تعرف ليه الـ BFS بيغلط مع الأوزان، وتكتب Dijkstra بـ min-heap، وليه d > dist[u] مش >=.
  • تبص على أي مسألة graph وتختار: BFS ولا DFS ولا topo sort ولا DSU ولا Dijkstra.

ليه الفصل ده؟ تلات أسئلة الـ BFS لوحده ما يحلهاش

في الفصلين اللي فاتوا كل مسألة كانت "امشي في الـ graph وعدّ". دلوقتي فيه تلات أنواع أسئلة بتتكرر في الاختبارات، وكل نوع ليه أداة:

السؤالمثال من الحياةالأداة
أرتّب الحاجات إزاي لو فيه حاجات لازم تخلص قبل حاجات؟ وهل ده ممكن أصلًا؟مواد الكلية: مفيش Data Structures قبل Programming 2.Topological sort
الاتنين دول في نفس المجموعة؟ والـ edges بتزيد واحد واحد.كابلات بتتمد بين data centers، وكل شوية حد يسأل: السيرفر ده يوصل للسيرفر ده دلوقتي؟Union-Find (DSU)
أقصر طريق لو كل طريق ليه وقت مختلف؟جوجل مابس: الدائري 25 دقيقة والمحور 40.Dijkstra

نبدأ بالأول. المواد دي، والسهم u → v معناه "خلّص u قبل v":

الرقمالمادةلازم قبلها
0Data Structures1, 5
1Programming 24
2Algorithms0, 5
3OOP1
4Programming 1ولا حاجة
5Discrete Mathولا حاجة

أول حل بييجي في دماغك: لف على المواد، وأول مادة كل شروطها خلصت خدها، وارجع لف من الأول.

بص عليه وهو شغال. الأحمر = لسه مش جاهزة، والأخضر = جاهزة، والـ teal = خلصت:

الترتيب صح، بس شوف الـ waste: كل لفة بتبدأ من الصفر وتلف على الـ edges تاني. ده ممكن يوصل لـ V × V × E، يعني 2000 مادة و 5000 شرط = حوالي 20 مليار عملية. Kahn هيعملها في O(V + E)، يعني حوالي 7000.

تشبيه ورق المصلحة الحكومية: كل شباك محتاج أختام من شبابيك تانية. بدل ما تلف على كل الشبابيك وتسأل "أقدر أدخل هنا؟"، كل شباك يكتب على بابه عدد الأختام الناقصة. كل ما تخلص شباك، تنقّص العداد عند اللي مستنيينه، وأول ما عداد يبقى صفر يدخل الطابور. العداد ده اسمه in-degree.

طب إزاي تعرف من كلام المسألة إنها محتاجة أنهي أداة من التلاتة؟ ده الجزء الجاي.

إزاي تعرف الأداة من المسألة

Topological sort:prerequisitesdependenciesmust be done beforebuild ordercan you finish allcycle in directed graph
Union-Find:are x and y connectedsame groupmergeedges added one by oneredundant edgea == b equations
Dijkstra:weighted edgesminimum cost / timenetwork delaycheapest routeminimum effort
ومش هما غالبًا لو:every step costs 1 (BFS)negative weights (Bellman-Ford)count all paths (DFS / DP)

أول counter-signal ده مهم: لو كل خطوة بنفس التمن ("أقل عدد moves")، ده BFS عادي، أبسط وأسرع. Dijkstra بيبقى لازم بس لما الخطوات تمنها مختلف.

flowchart TD
  A["Graph problem"] --> W{"Edges have different weights?"}
  W -- "yes, all non-negative" --> D["Dijkstra with a min-heap"]
  W -- no --> O{"Order with dependencies, or a cycle in a directed graph?"}
  O -- yes --> T["Topological sort: Kahn, or DFS with 3 colors"]
  O -- no --> U{"Edges arrive one by one, same group?, merge?"}
  U -- yes --> S["Union-Find (DSU)"]
  U -- no --> F{"Fewest steps?"}
  F -- yes --> B["BFS"]
  F -- no --> G["BFS or DFS: reach, count components"]
  

اسأل نفسك بالترتيب ده. أول سؤال دايمًا: الـ edges ليها أوزان مختلفة ولا لأ؟

أول أداة، الـ topological sort، شغالة على directed graph. يعني إيه directed بالظبط، وبنمثّله إزاي؟

Directed graph: لما الـ edge يبقى سهم

في الفصلين اللي فاتوا الـ edge كان بيمشي في الاتجاهين. هنا الـ edge سهم: u → v معناه تقدر تروح من u لـ v، مش العكس.

تشبيه الصحاب على فيسبوك undirected: لو أنا صاحبك يبقى إنت صاحبي. الفولو على انستجرام directed: إنت عامل فولو لمحمد صلاح، وهو مش عامل لك.
الـ cycle هنا معناها "مستحيل" عشان تطلع البطاقة محتاج شهادة ميلاد مميكنة، وعشان تطلع الشهادة محتاج البطاقة. ده cycle، ومفيش ترتيب في الدنيا يخلّصك. في مسائل الكورسات، cycle = الإجابة "مستحيل".
flowchart LR
  A((0)) --> B((1))
  A --> C((2))
  B --> D((3))
  C --> D
  X((5)) --> Y((6))
  Y --> Z((7))
  Z --> X
  

الشمال: الـ 3 بتتوصل من طريقين، بس ده مش cycle، لأنك ماشي مع الأسهم عمرك ما هترجع لـ node عديت عليها. اليمين: cycle حقيقي. افتكر الـ diamond ده، هيرجع لنا في الـ DFS.

التمثيل: adjacency list في اتجاه واحد + in-degree

نفس الـ adjacency list بتاعة الأساسيات، بفرق واحد: السهم بيتضاف في اتجاه واحد، ومعاه array بتعدّ الأسهم الداخلة:

  1. list لكل node. ليه مش new Array(n).fill([])؟ عشان fill([]) بيحط نفس الـ array في كل الخانات، فأي push بيظهر في الكل.
  2. الكل بيبدأ مش مستني حاجة. fill(0) هنا آمن لأن الصفر مش object.
  3. اقرا المسألة كويس: [u, v] معناه سهم من u لـ v ولا العكس؟ دي أكتر حتة الناس بتغلط فيها.
  4. ده الفرق الوحيد عن الـ undirected: مفيش adj[v].push(u). لو ضفته، هتقدر تمشي عكس السهم وكل حاجة هتبوظ.
  5. indeg[v]++ مش indeg[u]++: السهم داخل في v، فـ v هي اللي بقت مستنية حاجة زيادة.

كل خطوة بتضيف edge: الـ list بتكبر عند u (في الـ map)، والـ in-degree بيزيد عند v (الرقم تحت الـ node):

عندنا عدّاد الـ in-degree. إزاي نستخدمه عشان نطلّع الترتيب في لفة واحدة؟ ده Kahn.

Topological sort بـ Kahn's algorithm

Topological order = ترتيب لكل الـ nodes، وأي سهم u → v فيه u جاية قبل v. الـ key insight في Kahn إن الـ node اللي الـ in-degree بتاعها صفر مش مستنية حاجة، فممكن تيجي دلوقتي:

  1. ابدأ بالجاهزين: كل node الـ in-degree بتاعها صفر تدخل الـ queue.
  2. خلّص واحدة: طلّعها وحطها في الترتيب، وكل سهم u → v خارج منها يعمل indeg[v]--.
  3. جاهز جديد: لو indeg[v] بقى صفر، v تدخل الـ queue.
  4. في الآخر: الترتيب فيه n node؟ تمام. أقل؟ يبقى فيه nodes محبوسة في cycle.

الـ queue هنا نفس اللي في قالب الـ BFS: array عادية ومعاها head، من غير shift().

  1. الـ nodes من 0 لـ n - 1، و [u, v] معناه u قبل v. لو المسألة كاتبة الشرط بالعكس، اقلبه وإنت بتبني.
  2. البناء اللي لسه شايفينه.
  3. مش هنستخدم queue.shift(): بيزحزح كل العناصر، يعني O(n) كل مرة، والحل كله يبقى O(n²). الـ head بيحل ده.
  4. ليه نلف على كل الـ n؟ ممكن يبقى فيه أكتر من node جاهزة، وممكن مادة مالهاش ولا edge. دي in-degree بتاعها صفر ولازم تدخل الترتيب.
  5. < مش <=: لما head يحصّل length يبقى الـ queue فضي، و queue[queue.length] هيطلع undefined.
  6. queue[head++]: اقرا الأول، وبعدين زوّد head.
  7. u خلصت، فكل اللي بعدها مستني حاجة أقل.
  8. ليه === 0، ومش محتاجين visited؟ كل edge بينقّص مرة واحدة، فالـ indeg[v] بيعدّي على الصفر مرة واحدة بس في حياته. يعني كل node بتدخل الـ queue مرة بالظبط. الـ in-degree هنا هو الـ visited.
  9. أهم سطر. nodes الـ cycle كل واحدة مستنية التانية، فعمرها ما توصل صفر ولا تدخل الـ queue. لو نسيت السطر ده، هترجّع ترتيب ناقص كأنه إجابة.

على جدول المواد. الرقم تحت كل node هو الـ in-degree اللي فاضل، والـ nodes اللي في الـ queue حدودها متقطعة:

الترتيب: Programming 1، Discrete Math، Programming 2، Data Structures، OOP، Algorithms. وده مش الترتيب الوحيد: [5, 4, 1, 3, 0, 2] صح برضه، وأغلب المسائل بتقبل أي ترتيب صح.

ولو فيه cycle؟

نفس الكود على 1 → 2 → 3 → 1 ومعاهم 0 → 1. خلي عينك على الـ in-degree بتاع 1:

التعقيد: كل node بتدخل الـ queue مرة وتطلع مرة، وكل edge بنعدّي عليه مرة في البناء ومرة في التنقيص: O(V + E) وقت و memory.

Kahn خلص و order.length طلع 7 من 10. ده معناه إيه؟

  • فيه 3 nodes مالهمش أي edges
  • فيه cycle، والـ 3 الباقيين محبوسين فيه أو مستنيين حاجة محبوسة فيه
  • الكود فيه bug، المفروض دايمًا 10
  • الـ graph مش connected

الـ node اللي مالهاش edges بتدخل من الأول (in-degree صفر)، والـ graph المقطّع عادي. الحاجة الوحيدة اللي بتمنع node توصل صفر إنها مستنية حاجة عمرها ما هتخلص، وده بيحصل بس لو فيه cycle في الطريق.

Kahn بيكتشف الـ cycle بالعدّ. طب بالـ DFS اللي إنت عارفه؟ وليه الـ visited العادي هيغلط هنا؟

اكتشاف الـ cycle بالـ DFS أبو تلات ألوان

في الـ undirected graph، لو الـ DFS لقى neighbor متزار (ومش الأب)، يبقى فيه cycle. خد نفس الفكرة وطبّقها على الـ diamond (اللي مفيهوش cycle):

الـ false alarm ده سببه إن visited بيقول بس "اتزار". بس فيه نوعين: اتزار وهو لسه على الطريق الحالي (على الـ call stack)، ودي cycle. أو اتزار في طريق تاني خلص، زي الـ 3، وده عادي. عشان نفرّق، بنستخدم تلات حالات:

اللونمعناهلو السهم وصلني ليهفي الرسمة
White 0لسه ما اتزارشننزل لهمن غير لون
Gray 1دخلناه وما خلصناش (على الطريق الحالي)cycle! ده back edgeأصفر
Black 2خلص هو وكل اللي بعده، ومفيش cycleنعدّيهteal
تشبيه إنت في متاهة وماسك بكرة خيط بتفردها وإنت ماشي. لما توصل لطريق مسدود، ترجع وتلف الخيط وتكتب على باب الأوضة "خلصانة". لو دخلت أوضة فيها الخيط بتاعك (gray)، إنت لفيت في دايرة. لو مكتوب عليها "خلصانة" (black)، دي اتفتشت قبل كده ومفيهاش جديد.
  1. directed: سهم في اتجاه واحد. مش محتاجين in-degree هنا.
  2. Gray أول ما ندخل: "أنا على الطريق ده دلوقتي". الـ nodes الـ gray في أي لحظة هي بالظبط اللي على الـ call stack.
  3. Gray = cycle. v gray يعني فيه طريق v → … → u، والسهم u → v بيقفل الدايرة. بنعمل early return بـ true.
  4. أبيض؟ ننزل له، ولو لقى cycle نوصّل الـ true لفوق. وأسود؟ ولا شرط بيتحقق فبنعدّيه، لأنه اتفتش ومش على الطريق الحالي، فمش ممكن يقفل دايرة.
  5. Black لما نخلص، مش white. لو رجّعته أبيض زي الـ backtracking، كل طريق يوصل له هيفتّشه من الأول، والوقت ممكن يبقى exponential.
  6. الـ graph ممكن يبقى حتت، والـ cycle ممكن تبقى في حتة الـ DFS الأول ما وصلهاش. زي الـ components: نبدأ من كل node لسه بيضا.

على graph فيه الحالتين: diamond (0 → 1 → 3 و 0 → 2 → 3) و cycle (2 → 4 → 5 → 2):

التعقيد: كل node بيتعمل لها dfs مرة (وهي بيضا)، وكل سهم بنبص عليه مرة: O(V + E).

عمق الـ recursion لو الـ graph سلسلة 100,000 node، الـ recursion عمقه 100,000، و JS بيضرب Maximum call stack size exceeded عند عمق حوالي 10,000 (بيختلف حسب البيئة). Kahn مفيهوش recursion، فهو أأمن في الـ inputs الكبيرة. قول ده في الانترفيو.
Topological order من الـ DFS حط post.push(u) جنب color[u] = BLACK، وفي الآخر اعمل post.reverse(): هيطلعلك topological order صح، لأن كل node بتتحط بعد كل اللي بعدها.

عندك أداتين للـ cycle: Kahn و الـ 3 colors. يلا على أول مسألة حقيقية.

مثال محلول 1: Course Schedule

Course Schedule

mediumLeetCode 207

عندك numCourses مادة من 0 لـ numCourses - 1، و list شروط. الشرط [a, b] معناه: عشان تاخد a لازم تكون خلصت b. ينفع تخلص كل المواد؟

Input: numCourses = 5, prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3]] Output: true (0, 1, 2, 3, 4 works) Input: numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]] Output: false (0 needs 1, 1 needs 2, 2 needs 0)

الجديد هنا إن المسألة مش بتقولك "graph" خالص. لازم إنت اللي تترجم الشروط لأسهم، وتعرف إن "ينفع؟" معناها "مفيش cycle؟".

  1. اتجاه السهم: [a, b] يعني b الأول، فالسهم b → a. الترتيب في الـ pair عكس الترتيب في الوقت، وده trap.
  2. Brute force: جرّب كل ترتيبات المواد: n!، يعني 10 مواد بس = 3.6 مليون. مستحيل.
  3. الـ key insight: ترتيب موجود ⟺ مفيش cycle. فالمسألة هي "فيه cycle في directed graph؟"، وهنحلها بالـ 3 colors.
  4. Edge cases: مفيش شروط (true)، مادة شرط لنفسها [0, 0] (false)، مواد ملهاش علاقة ببعض.
  1. أهم سطر. b الأول، فالسهم adj[b].push(a). هنا لو قلبته الإجابة هتطلع صح بالصدفة (قلب كل الأسهم بيسيب الـ cycle cycle)، بس في Course Schedule II الترتيب هيطلع مقلوب. اكتبها صح من الأول.
  2. 0 أبيض، 1 رمادي، 2 أسود.
  3. نفس الـ DFS اللي في القالب بالظبط.
  4. الدالة بتسأل "ينفع؟"، فأول cycle نرجّع false. خلي بالك من القلب: hasCycleFrom بترجّع true لما الحاجة وحشة.
Inputالمتوقعليه مهمة
n = 3, []trueمفيش أسهم خالص
n = 3, [[0,0]]falseself-loop: 0 بتلاقي سهم لنفسها وهي gray
n = 2, [[1,0],[0,1]]falseأصغر cycle بين مادتين
n = 4, [[1,0],[3,2]]trueحتتين: الـ loop اللي برا بتبدأ DFS جديد من 2

التعقيد: O(V + E) وقت و memory (V المواد، E الشروط).

في الانترفيو ابدأ بجملة: "المسألة دي هي: فيه cycle في directed graph؟". بعدها قول إن فيه حلّين، واختار واحد: Kahn من غير recursion، والـ DFS أقصر في الكتابة.

طب لو المسألة عايزة الترتيب نفسه، مش بس "ينفع ولا لأ"؟

مثال محلول 2: Course Schedule II

Course Schedule II

mediumLeetCode 210

نفس المسألة، بس رجّع ترتيب تاخد بيه كل المواد (أي ترتيب صح ينفع). ولو مستحيل، رجّع array فاضية.

Input: numCourses = 5, prerequisites = [[0,3],[1,3],[1,4],[2,0],[2,1]] Output: [3, 4, 0, 1, 2] (any valid order is accepted) Input: numCourses = 2, prerequisites = [[0,1],[1,0]] Output: []

الجديد هنا إن المطلوب الترتيب نفسه، فـ Kahn أنسب لأن الترتيب بيطلع منه على طول. وفيه trick صغير: مش محتاجين array اسمها order خالص.

  1. ليه؟ في قالب head العناصر مش بتتمسح. كل node بتدخل الـ queue مرة وتطلع بنفس ترتيب دخولها، فالـ queue نفسها في الآخر هي الترتيب.
  2. Edge cases: cycle ([])، مادة واحدة ([0])، مفيش شروط ([0, 1, 2, …]).
  1. السهم b → a، و a هي اللي مستنية، فـ indeg[a]++. لو كتبت indeg[b]++ الترتيب هيطلع مقلوب أو [] غلط.
  2. لو مفيش ولا مادة من غير شروط، الـ queue فاضي والإجابة []، وده صح: كل مادة ليها شرط يبقى أكيد فيه cycle.
  3. Kahn بالحرف، من غير order.push.
  4. في الآخر head === queue.length، يعني كل اللي في الـ array خلص بالترتيب. لو طولها أقل من numCourses، فيه cycle.

السطر queue بيوريك الـ array كلها، واللي قبل head خلص (teal):

Inputالمتوقعليه مهمة
1, [][0]مادة واحدة
2, [[0,1],[1,0]][]cycle: الـ queue بيبدأ فاضي
3, [[1,0],[1,2],[0,1]][]2 بتطلع، بس 0 و 1 محبوسين، فالطول 1 مش 3

التعقيد: O(V + E)، زي القالب.

كده سؤال الترتيب خلص. السؤال التاني: الـ edges بتيجي واحد واحد، وعايز تعرف مين مع مين بسرعة.

Union-Find: الفكرة من الصفر

عندك 8 سيرفرات، والشركة بتمد كابلات بينهم واحد واحد. وبين كل كابل والتاني حد بيسأل: "3 يوصل لـ 7 دلوقتي؟". الحل البديهي BFS مع كل سؤال، يعني O(V + E) لكل سؤال. مع 100,000 سيرفر و 100,000 سؤال، ده حوالي 10 مليار عملية. TLE.

الفكرة: بدل ما نمشي في الـ graph كل مرة، نفتكر كل سيرفر في أنهي مجموعة. كل مجموعة ليها leader (اسمه root أو representative)، و"نفس المجموعة؟" تبقى "نفس الـ leader؟". ولما كابل يربط مجموعتين، ندمجهم.

تشبيه عيلة كبيرة في الصعيد، وكل واحد عارف أبوه بس. عشان تعرف اتنين من نفس العيلة، كل واحد يسأل أبوه، وأبوه يسأل أبوه، لحد كبير العيلة. نفس الكبير = نفس العيلة. ولما عيلتين يتناسبوا، كبير واحد فيهم يبقى تابع للتاني، وخلاص.

لو رسمت سهم من كل i لـ parent[i] هتلاقي forest: كل مجموعة شجرة والـ leader فوق.

المشكلة: السلسلة الطويلة، وحلّين ليها

لو دمجت بغباء ممكن تطلع سلسلة طولها n، و find ترجع O(n). تحسينين، ومع بعض كل عملية تبقى تقريبًا O(1):

  1. Union by size: الشجرة الصغيرة تتعلّق تحت الكبيرة. عمق أي node بيزيد بس لما مجموعتها تتدمج في واحدة قدّها أو أكبر، يعني الحجم بيتضاعف، فالعمق عمره ما يعدّي log₂ n.
  2. Path compression: وإنت راجع من find، كل node عدّيت عليها تشاور على الـ leader مباشرة. زي ما توصل لعنوان وتكتبه في ورقة عشان المرة الجاية.

مع الاتنين، الـ amortized cost لكل عملية O(α(n))، و α أقل من 5 لأي n هتشوفه. في الانترفيو قول "تقريبًا O(1) amortized".

  1. [0, 1, …, n - 1]: الـ function بتاخد (القيمة، الـ index) وبترجّع الـ index. كل واحد leader لنفسه.
  2. size[r] = حجم المجموعة. صح عند الـ leaders بس، والباقي محدش بيبص عليه.
  3. count = عدد المجموعات، وبينقص مع كل دمج. ده عدد الـ connected components ببلاش.
  4. السطر ده بيعمل حاجتين: بيجيب الـ leader بالـ recursion، وبيحطه في parent[x] وهو راجع. وكل نداء في السلسلة بيعمل كده، فكل اللي في الطريق بيتربط بالـ leader. ده الـ path compression.
  5. parent[x] مش x: بعد السطر اللي فوق، parent[x] هو الـ leader.
  6. دايمًا اشتغل على الـ leaders. union(a, b) معناها "ادمج مجموعة a مع مجموعة b"، فلازم الـ roots الأول.
  7. نفس الـ leader؟ مفيش دمج. والـ false دي مفيدة: معناها "الـ edge ده بيقفل cycle".
  8. swap عشان ra يبقى الأكبر، والـ root الصغير يتعلّق تحته. مش parent[b] = a: ده بيربط عنصر بعنصر، ولو b مش leader هيقطعه من مجموعته.
  9. الـ size عند الـ leader الجديد، والعدد نقص واحد، و true = حصل دمج فعلًا.

الـ parent والـ forest مع بعض. كل مجموعة ليها لون، والـ size الحقيقي مكتوب عند الـ leader بس. خلي بالك من union(6, 4): المجموعة الأكبر بتفضل فوق حتى لو جت تانية في النداء (الـ swap). وبعدين find(1) هيوريك الـ path compression في الـ call stack:

parent = [0, 0, 1, 2, 4] من غير path compression. find(3) بيرجّع كام، وبيمشي كام خطوة؟

  • بيرجّع 2، خطوة واحدة
  • بيرجّع 0، بيمشي 3 → 2 → 1 → 0
  • بيرجّع 3، لأن parent[3] مش 3
  • بيرجّع 4

parent[3] = 2 ثم 1 ثم 0، و parent[0] = 0 فده الـ leader. ومع path compression الـ array هتبقى بعدها [0, 0, 0, 0, 4].

جرّب الـ DSU على مسألة الـ data centers نفسها: تقسيم الشبكة لمناطق.

مثال محلول 3: Number of Provinces بالـ DSU

Number of Provinces

mediumLeetCode 547

عندك n data center ومصفوفة isConnected: لو isConnected[i][j] = 1 فيه كابل مباشر بين i و j. المنطقة = مجموعة بتوصل لبعض مباشرة أو من خلال غيرها. كام منطقة؟

Input: isConnected = [[1,1,0,1,0,0], [1,1,0,1,0,0], [0,0,1,0,0,1], [1,1,0,1,0,0], [0,0,0,0,1,0], [0,0,1,0,0,1]] Output: 3 ({0, 1, 3}, {2, 5}, {4})

دي نفس المسألة اللي حليناها بالـ DFS في فصل الأساسيات، واللي بتيجي في الـ online assessments باسم "قسّم شبكة الـ data centers لمناطق". الجديد هنا إن الأداة اتغيرت: بدل ما نمشي في الـ graph، كل 1 في المصفوفة بقى union، والإجابة هي count ببلاش.

  1. الترجمة: كل 1 = edge، والمنطقة = connected component.
  2. الخطة: ابدأ بـ n منطقة، واعمل union لكل 1. كل دمج ناجح بيقلّل واحد.
  3. توفير: المصفوفة متماثلة والقطر كله 1، فكفاية النص اللي فوق القطر: j > i.
  1. في الأول count = n: كل data center منطقة لوحده.
  2. ليه j = i + 1 مش 0؟ [i][j] و [j][i] نفس الكابل، والقطر معناه "موصّل بنفسه". من 0 هتعمل union مرتين على الفاضي.
  3. لو الاتنين أصلًا منطقة واحدة (زي [1][3]: اتربطوا عن طريق 0)، الـ union بيرجّع false و count ما بيتغيرش.
  4. n ناقص الدمجات الناجحة، والـ DSU بيعدّها لوحده.

الصف اللي بنلف عليه أزرق، والـ 1 اللي بنعالجه أصفر، والـ forest تحت بيتغير مع كل دمج:

Inputالمتوقعليه مهمة
[[1]]1data center واحد: الـ loops مش بتدخل
[[1,0],[0,1]]2ولا كابل: count فاضل n
المثال3الكابل [1][3] زيادة

التعقيد: n²/2 خانة وكل union تقريبًا O(1): O(n²) وقت زي الـ DFS، و O(n) memory. الـ DSU بيكسب لما الكابلات تيجي واحد واحد ومعاها أسئلة في النص.

هنا لما union رجّع false عدّيناه. طب لو الـ false ده هو المطلوب بالظبط؟

مثال محلول 4: Redundant Connection

Redundant Connection

mediumLeetCode 684

كان عندك tree فيها n node من 1 لـ n (connected ومفيهاش cycle)، وحد ضاف edge زيادة، فبقوا n edge. رجّع edge لو شلته ترجع tree، ولو فيه أكتر من إجابة رجّع آخر واحد في الـ input.

Input: edges = [[1,2],[1,3],[3,4],[2,5],[4,5],[3,6]] Output: [4,5] Input: edges = [[1,2],[2,3],[1,3]] Output: [1,3]

الجديد هنا إن الـ false اللي union بيرجّعه هو الإجابة نفسها: edge طرفيه أصلًا متوصلين = edge بيقفل cycle.

  1. Brute force: شيل كل edge من الآخر واعمل DFS تتأكد إن الباقي tree: O(n²).
  2. الـ key insight: ضيف الـ edges بالترتيب في الـ DSU. أول edge طرفيه في نفس المجموعة يبقى فيه طريق بينهم من غيره، فهو بيقفل الـ cycle الوحيدة.
  3. ليه هو "آخر واحد"؟ كل edges الـ cycle اللي قبله اتضافوا عادي، وهو اللي قفل الدايرة، يعني هو آخر واحد فيهم في الـ input.
  1. tree بـ n node فيها n - 1 edge، وواحد زيادة يبقوا n. فعدد الـ nodes = عدد الـ edges.
  2. Off-by-one كلاسيكي. الـ nodes من 1 لـ n. مع new DSU(n)، parent[n] هيبقى undefined، و find(n) هتنادي find(undefined) لحد ما الـ stack يضرب. فبنعمل n + 1 ونسيب الخانة 0.
  3. أول false = الإجابة، فبنعمل early return.

الـ edges اللي لسه ما اتضافتش باهتة، والـ nodes اللي في نفس المجموعة ليها نفس اللون:

Inputالمتوقعليه مهمة
[[1,2],[2,3],[1,3]][1,3]أصغر cycle
[[1,2],[1,3],[2,3]][2,3]نفس المثلث بترتيب تاني: الإجابة بتتغير
[[2,3],[3,4],[2,4],[4,1]][2,4]بنرجع قبل ما نوصل لـ [4,1]

التعقيد: n عملية union: O(n · α(n)) ≈ O(n) وقت، و O(n) memory.

لقينا الـ edge الزيادة وشلناه. طب لو عايزين نستخدمه في حتة تانية؟

مثال محلول 5: Number of Operations to Make Network Connected

Make Network Connected

mediumLeetCode 1319

عندك n كمبيوتر من 0، و list كابلات. تقدر تفك أي كابل وتوصّله بين أي جهازين. أقل عدد نقلات عشان الكل يوصل لبعض؟ ولو مستحيل رجّع -1.

Input: n = 6, connections = [[0,1],[0,2],[1,2],[3,4],[0,3]] Output: 1 (move the spare cable 1-2 to connect 5) Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] Output: -1 (4 cables can never connect 6 computers)

الجديد هنا إن بنستخدم الحاجتين مع بعض: count بيقولنا محتاجين كام نقلة، والـ false بيقولنا عندنا كام كابل زيادة.

  1. الاستحالة: n جهاز محتاجين n - 1 كابل على الأقل. أقل من كده؟ -1.
  2. العدّ: لو فيه k مجموعة، كل نقلة بتربط اتنين، فمحتاجين k - 1.
  3. الكابلات كفاية؟ المجموعات محتاجة n - k كابل عشان تفضل متوصلة، والباقي زيادة. ولو الكابلات ≥ n - 1 يبقى الزيادة ≥ k - 1، يعني دايمًا كفاية.
  1. كل كابل بيقلّل المجموعات واحد بالكتير، فمن n لواحدة محتاج n - 1. و < مش <=: n - 1 بالظبط ممكن يكفّوا.
  2. اللي union بتاعه رجّع false ده الكابل الزيادة اللي هننقله.
  3. كله متوصل؟ count = 1 والإجابة 0.
Inputالمتوقعليه مهمة
n = 1, []0جهاز واحد
n = 4, [[0,1],[0,2],[1,2]]13 كابلات = n - 1 بالظبط، وواحد زيادة يتنقل لـ 3
n = 6, [[0,1],[0,2],[0,3],[1,2]]-14 أقل من 5

التعقيد: O(n + E · α(n)) وقت، و O(n) memory.

لحد هنا كل edge زي التاني. لو كل edge ليه وقت مختلف، الـ BFS لسه هيجيب أقصر طريق؟

Dijkstra: ليه الـ BFS بيغلط مع الأوزان

في weighted graph كل edge عليه رقم: وقت أو مسافة أو فلوس. الـ edge بيبقى [u, v, w]، وطول الطريق = مجموع الأوزان، مش عدد الـ edges.

الـ BFS ليه ضمان واحد: أول مرة يوصل لـ node، بيكون وصلها بأقل عدد edges، لأنه بيمشي طبقات. بس مع الأوزان، edge واحد وزنه 7 أطول من 3 edges وزنهم 1 و 2 و 1. خد الـ BFS وخلّي dist[u] + 1 تبقى dist[u] + w:

المشكلة في if (dist[v] === -1): الـ BFS بيقفل المسافة أول ما يشوف الـ node، وده صح بس لما كل الخطوات بنفس التمن.

الفكرة: الأقرب الأول

بدل FIFO، نطلّع دايمًا الـ node اللي مسافتها المعروفة أصغر حاجة. ولما node تطلع، مسافتها تبقى final. ولو لقينا طريق أقصر لـ node لسه ما طلعتش، نحدّثها عادي.

تشبيه دلق مية من محطة البداية، والمية بتمشي في كل الشوارع بنفس السرعة. أول مكان توصله هو الأقرب ليك بالوقت مش بعدد الشوارع، وبعده التاني في القرب، وهكذا. Dijkstra بيقلّد المية دي.

ليه الـ node اللي بتطلع مسافتها final؟ لو u هي الأقرب من اللي لسه ما خلصوش بمسافة d، أي طريق تاني ليها لازم يعدّي على node لسه ما خلصتش ومسافتها ≥ d، وبعدها الأوزان مش سالبة فالطريق مش هيقصر. يعني مفيش أقل من d.

الأوزان السالبة بتكسر الإثبات ده edge سالب ممكن ينزّل طريق تحت d بعد ما قفلنا u. نسخة الـ visited هتطلّع إجابة غلط. ونسختنا (lazy) هتدخّل الـ node تاني وتصلّح نفسها، بس الوقت ممكن يبقى exponential، ولو فيه cycle مجموعها سالب مش هتخلص أبدًا. الأوزان السالبة ليها Bellman-Ford.

نجيب "الأقرب" إزاي بسرعة؟ لو لفينا على كل الـ nodes كل مرة يبقى O(V²). الـ min-heap بيدّينا الأصغر في O(log n)، وده الـ priority queue اللي بيحل محل الـ queue العادي.

الفكرة: الأقرب الأول بـ heap. إزاي تبقى كود؟

القالب: Dijkstra بـ min-heap

JS مالهاش heap built-in. في LeetCode فيه library جاهزة، بس في HackerRank وفي الانترفيو مش مضمونة، فاعرف تكتب واحد صغير. ده بيقارن بأول خانة بس، والتفاصيل في فصل الـ Heap:

  1. شجرة متخزّنة في array: الـ root في a[0]، وكل أب أصغر من ولاده، فالأصغر دايمًا في a[0]. العنصر [dist, node] والمقارنة بـ [0].
  2. الجديد بيتحط في الآخر. أبو الخانة i هو (i - 1) >> 1، يعني Math.floor((i - 1) / 2)، والولاد 2i + 1 و 2i + 2.
  3. طول ما الأب أكبر، بدّلهم واطلع. العمق log n، فالـ push بـ O(log n).
  4. بنحفظ الـ root عشان نرجّعه، ونحط آخر عنصر مكانه. ولو الـ heap كان فيه عنصر واحد، خلاص فضي.
  5. نبدّل مع أصغر ابن وننزل، عشان اللي يطلع فوق يبقى أصغر من أخوه كمان. برضه O(log n).

ودلوقتي Dijkstra نفسه. حط عينك على السطر 9:

  1. كل عنصر في adj[u] هو [v, w]، ولازم كل الأوزان ≥ 0.
  2. ليه Infinity مش -1؟ الشغل كله مقارنات <، وأي طريق حقيقي أصغر من Infinity تلقائي. ولو فضلت Infinity في الآخر، الـ node دي مش reachable.
  3. الترتيب جوه الـ pair مهم: [dist, node]، لأن الـ heap بيقارن بأول خانة. لو قلبتهم، هيطلّع أصغر رقم node والحل يبوظ من غير error.
  4. طلّع الأقرب: ده الـ greedy step.
  5. Lazy deletion. لما بنلاقي طريق أقصر لـ v مش بنعدّل الـ entry القديمة، بنزوّد واحدة جديدة. القديمة لما تطلع هتبقى d > dist[u]، يعني stale، فنرميها. وليه > مش >=؟ الـ entry الصح بتطلع و d === dist[u]. مع >=، أول pop [0, src] نفسه هيترمي، وكل المسافات تفضل Infinity.
  6. ده الـ relaxation: طريق عن طريق u أقصر من اللي نعرفه؟ و < مش <=: طريق بنفس الطول مش هيغيّر حاجة.
  7. نحدّث وندخّل entry جديدة. لو v ليها entry قديمة، بقت stale وسطر 9 هيرميها.

الرقم تحت كل node هو أقصر مسافة معروفة، والـ heap مرسوم مترتب: أول واحد هو اللي هيطلع، وكل entry (المسافة، الـ node). الـ stale بالأحمر، والـ edges المتلونة هي أقصر الطرق:

BFSDijkstra
الـ edgesمن غير أوزانأوزان مختلفة، ≥ 0
الطابورqueue: FIFOmin-heap: الأقرب الأول
المسافة بتتقفل إمتىلما الـ node تدخل (visited on push)لما الـ node تطلع من الـ heap
الـ node بتدخل كام مرةمرة واحدةممكن أكتر، والزيادة stale
ComplexityO(V + E)O((V + E) log V)

التعقيد بالعدّ: كل edge بيعمل push واحد بالكتير، فالـ heap بيستقبل E + 1 entry بالكتير، وكل push و pop بـ O(log E)، و log E ≤ 2 log V. المجموع O((V + E) log V) وقت، و O(V + E) memory.

لو شلت if (d > dist[u]) continue; خالص، إيه اللي يحصل؟

  • الإجابة تطلع غلط
  • loop ما بتخلصش
  • الإجابة صح، بس كل entry قديمة هتلف على الـ neighbors على الفاضي
  • error

الـ entry القديمة d بتاعتها أكبر، فأي d + w مش هيحسّن حاجة اتجرّبت قبل كده بالمسافة الأصغر. الإجابة صح، بس في graph كبير ده waste جامد. السطر ده optimization، مش correctness.

يلا نشغّل القالب على مسألة شبكة حقيقية.

مثال محلول 6: Network Delay Time

Network Delay Time

mediumLeetCode 743

شبكة فيها n جهاز من 1 لـ n. كل [u, v, w] في times معناه إشارة من u بتوصل v بعد w (اتجاه واحد). بعتنا إشارة من k. بعد قد إيه كل الأجهزة توصلها؟ ولو جهاز عمره ما هيوصله حاجة، -1.

Input: times = [[1,2,5],[1,3,1],[3,2,2],[2,4,1],[3,4,6],[4,5,2]], n = 5, k = 1 Output: 6 (node 5 is the last one: 1 → 3 → 2 → 4 → 5 = 1 + 2 + 1 + 2) Input: times = [[1,2,1]], n = 2, k = 2 Output: -1 (from 2 you can't reach 1)

الجديد هنا إن الإجابة مش dist نفسها: الإشارة بتمشي في كل الطرق مع بعض، فالكل استلم لما آخر واحد يستلم، يعني max(dist). وكمان الـ graph directed والـ nodes من 1.

  1. الأداة: أوزان مختلفة ومش سالبة، من بداية واحدة: Dijkstra من k.
  2. الإجابة: max(dist[1..n])، ولو فيه Infinity يبقى -1.
  3. Edge cases: جهاز واحد (0)، جهاز مش reachable (-1)، واتجاه الـ edges.
  1. n + 1 عشان الـ nodes من 1، والخانة 0 مش مستخدمة. أسهل من إنك تطرح 1 من كل رقم.
  2. directed: مفيش adj[v].push([u, w]).
  3. القالب بالحرف (d + w مكان nd).
  4. هنا الـ off-by-one بيستخبى. لو بدأت من i = 0، dist[0] = Infinity فالإجابة هتطلع -1 دايمًا. ولو i < n، هتنسى آخر جهاز وممكن يكون هو الأبطأ. و max مش sum، لأن الإشارة بتمشي في كل الطرق في نفس الوقت.
  5. أي جهاز Infinity يخلّي الـ max Infinity، فنرجّع -1.
Inputالمتوقعليه مهمة
[], n = 1, k = 10الجهاز اللي بعت هو الوحيد
[[1,2,1]], n = 2, k = 2-1الاتجاه: من 2 مفيش سهم خارج
[[1,2,1],[2,3,2],[1,3,4]], n = 3, k = 13المباشر (4) أطول من اللي بيعدّي على 2

التعقيد: O((n + E) log n) وقت (E = times.length)، و O(n + E) memory.

طب لو تكلفة الطريق مش مجموع، والـ graph كمان grid؟

مثال محلول 7: Path With Minimum Effort (Dijkstra على grid)

Path With Minimum Effort

mediumLeetCode 1631

grid ارتفاعات. هتمشي من الشمال فوق لليمين تحت في أربع اتجاهات. مجهود الطريق = أكبر فرق ارتفاع بين خانتين ورا بعض فيه. عايز أقل مجهود.

Input: heights = [[1,3,2], [6,8,3], [2,4,5]] Output: 2 (1 → 3 → 2 → 3 → 5: the steps are 2, 1, 1, 2, the biggest is 2)

الجديد هنا إن تكلفة الطريق max مش sum، والـ graph grid. Dijkstra لسه شغال؟ أيوه، لأن الإثبات محتاج حاجة واحدة: التكلفة ما بتقلّش وإنت بتطوّل الطريق، والـ max عمره ما بيقل.

  1. الـ grid graph: كل خانة node، والجيران بالـ DIRS والـ bounds check زي فصل الـ Grid، ووزن الخطوة = فرق الارتفاع.
  2. التغيير الوحيد: Math.max(e, w) مكان d + w.
  3. Early return: أول ما الخانة الأخيرة تطلع من الـ heap، مجهودها final.
  4. حل تاني: binary search على الإجابة + BFS بالخطوات اللي فرقها ≤ X. برضه مقبول.
  1. الـ dist هنا 2D، وكل صف array جديدة (نفس فخ fill).
  2. [effort, r, c]: المجهود الأول لأن الـ heap بيقارن بأول خانة.
  3. نرجّع لما الهدف يطلع مش لما يدخل. وهو داخل ممكن يبقى فيه طريق أحسن لسه ما اتكتشفش. وهو طالع، هو الأقرب من كل اللي فاضل.
  4. bounds check: >= R مش > R، لأن آخر index هو R - 1.
  5. قلب المسألة: الأكبر بين مجهود اللي فات وفرق الخطوة دي، و Math.abs لأن النزول زي الطلوع.
  6. مش هيتنفّذ: الهدف دايمًا reachable، والـ grid خانة واحدة بترجع من سطر 11.

الارتفاعات فوق، و effort صف صف تحتها. اللي خلص teal:

التعقيد: V = R × C و E ≈ 4V، فالوقت O(R · C · log(R · C)) والـ memory O(R · C).

كده الأدوات كلها معاك. فين الناس بتقع وهي بتكتبها؟

غلطات مشهورة

كلها بتطلّع Wrong Answer أو TLE من غير error، فبتاخد وقت عشان تلاقيها.

1. قلبت اتجاه الشرط

الصح adj[b].push(a) و indeg[a]++. قبل ما تكتب اسأل: "مين لازم يخلص الأول؟ هو ده بداية السهم".

2. ربطت العناصر بدل الـ leaders

لو b مش leader، السطر ده بيفصله عن أبوه، فمجموعته القديمة بتتقسم وإنت مش واخد بالك. دايمًا root بـ root.

3. في Dijkstra قفلت الـ node وهي داخلة زي الـ BFS

دي بالظبط غلطة الـ BFS اللي شفناها. المسافة بتتقفل لما الـ node تطلع. ولو عايز visited، حطه بعد الـ pop: if (visited[u]) continue; visited[u] = true; بدل سطر الـ stale.

4. الـ nodes من 1 لـ n والـ array طولها n

أول ما تقرا "labeled from 1 to n"، اكتب n + 1 في كل array و i = 1 لحد i <= n. نفس نوع i < n و i <= n في FizzBuzz، بس هنا بيدّيك -1 غلط من غير ما يضرب.

اختبر نفسك قبل ما تروح LeetCode.

اختبر نفسك

DSU من غير path compression ومن غير union by size. الـ worst case لـ find واحدة؟

  • O(1)
  • O(log n)
  • O(n)، لأن الشجرة ممكن تبقى سلسلة
  • O(n²)

لو دايمًا ربطت الكبير تحت الصغير، تطلع سلسلة طولها n. Union by size لوحده بيخلّي العمق O(log n)، ومع path compression تقريبًا O(1).

في Dijkstra، ليه d > dist[u] ومش d >= dist[u]؟

  • مش فارقة
  • الـ entry الصح بتطلع و d === dist[u]، و >= هترميها هي كمان
  • عشان الأوزان ممكن تبقى صفر
  • عشان نتجنب الـ Infinity

أول pop هو [0, src] و dist[src] = 0. مع >= هيترمي، والـ heap يفضى، وكل حاجة تفضل Infinity.

الـ edges بتيجي واحد واحد، وبينهم أسئلة "x و y متوصلين؟". 100,000 من كل نوع. أحسن حاجة؟

  • BFS مع كل سؤال
  • DFS مع كل سؤال
  • Union-Find: union مع كل edge، و find(x) === find(y) مع كل سؤال
  • Dijkstra

الـ BFS مع كل سؤال حوالي 1010 في المجموع. الـ DSU حوالي 200,000 عملية. ده بالظبط اللي اتعمل عشانه.

graph فيه edge وزنه -3. أنهي جملة صح؟

  • Dijkstra شغال عادي، الـ heap بيرتّب أي أرقام
  • ضمان "اللي طلع من الـ heap مسافته final" بيبوظ، فـ Dijkstra مش الأداة الصح
  • نزوّد رقم كبير على كل الأوزان عشان تبقى موجبة
  • الكود هيضرب error

مثال: 0 → 1 بـ 2، و 0 → 2 بـ 5، و 2 → 1 بـ -4، و 1 → 3 بـ 1. الـ 1 بتطلع بـ 2 وتخلّي 3 = 3، وبعدين 2 تلاقي 1 بـ 1. نسخة الـ visited هتسيب 3 على 3 والصح 2. وزيادة رقم ثابت غلط، لأن الطريق اللي فيه edges أكتر بياخد زيادة أكتر. الصح Bellman-Ford.

تمرين: فكّر قبل ما تفتح

Satisfiability of Equality Equations

mediumLeetCode 990

list معادلات، كل واحدة 4 حروف: يا "x==y" يا "x!=y"، والمتغيرات حروف إنجليزي صغيرة. ينفع تدّي كل حرف رقم، وكل المعادلات تطلع صح؟

["p==q", "q==r", "r!=p"] → false (p = q = r, so r != p can't hold) ["p==q", "r!=s"] → true ["p!=p"] → false
تلميح 1

الـ == بتعمل مجموعات: p == q و q == r يبقى الـ 3 مجموعة واحدة. ده شكله إيه من اللي في الفصل؟

تلميح 2

DSU بـ 26 عنصر. الأول union لكل الـ ==، وبعدين لكل !=: نفس الـ leader يبقى مستحيل. ليه لفتين مش لفة واحدة؟

الحل

ليه لفتين؟ لو لفة واحدة، ممكن "r!=p" تيجي قبل "p==q" و "q==r"، فوقتها r و p لسه منفصلين وهتقول "تمام" غلط. المجموعات لازم تكمل الأول. و "p!=p" بتطلع false لوحدها لأن find(p) === find(p).

جاهز؟ دي المسائل بالترتيب.

اتمرن على LeetCode بالترتيب

topo sort الأول، بعدين DSU، بعدين Dijkstra، وفي الآخر مسائل بتجمع. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للقالب هنا، وبعدين حاول تاني من غير ما تبص.

وفي الآخر، الفصل كله في صفحة واحدة.

الخلاصة

في جملة واحدة شروط وترتيب = Kahn (والـ in-degree هو العدّاد)، ومجموعات بتتدمج = Union-Find (root بـ root)، وأوزان مش سالبة = Dijkstra (طلّع الأقرب، وارمي الـ stale). ومن غير أوزان، الـ BFS لسه هو الملك.
المسألة بتقولالأداةComplexity
أقصر طريق، كل خطوة بنفس التمنBFSO(V + E)
أقصر طريق، أوزان مختلفة ومش سالبةDijkstra + min-heapO((V + E) log V)
أوزان سالبة، أو عدد محطات محدودBellman-Ford (برا الفصل)O(V · E)
ترتيب بشروط، أو "ينفع تخلص كله؟"Topological sort: Kahn أو DFS 3 colorsO(V + E)
الـ edges بتيجي واحد واحد، "متوصلين؟"، دمجUnion-Find≈ O(1) لكل عملية
edge زيادة / cycle في undirected graphUnion-Find (union بيرجّع false)≈ O(E)
عدّ الـ components (graph ثابت)BFS أو DFS أو Union-FindO(V + E)
grid: جزر، flood fill، أقل خطواتBFS / DFS على الـ gridO(R · C)

الفصل الجاي: Backtracking. الـ DFS اللي استخدمته هنا (انزل، كمّل، ارجع) هو نفسه هيكل الـ backtracking، بس هتمشي في شجرة اختيارات بتبنيها وإنت ماشي. وفاكر "ما ترجّعش الـ node بيضا عشان الوقت ما يبقاش exponential"؟ في الـ backtracking هتعمل كده بالظبط عن قصد، عشان تجرّب كل الطرق. وبعده Greedy هيرجّعلك فكرة Dijkstra: خد أحسن حاجة قدامك دلوقتي، وإمتى ده يبقى صح.

إزاي الـ DFS ده نفسه يجرّب كل الاحتمالات بنظام؟ ده الفصل الجاي.