Topological Sort و Union-Find و Dijkstradirected graphs · Kahn · 3-color DFS · DSU · Dijkstra
في الأساسيات اتعلمت BFS و DFS، وفي فصل الـ Grid طبّقتهم على جزر وبرتقان بايظ. كل ده كان سؤال واحد: مين يوصل لمين، وفي كام خطوة. دلوقتي هنجاوب على تلات أسئلة أصعب: ترتّب حاجات ليها شروط إزاي، تعرف مين مع مين والـ edges بتيجي واحد واحد، وأقصر طريق لما كل edge ليه وزن.
هتطلع من الفصل ده وإنت عارف
- يعني إيه 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":
| الرقم | المادة | لازم قبلها |
|---|---|---|
| 0 | Data Structures | 1, 5 |
| 1 | Programming 2 | 4 |
| 2 | Algorithms | 0, 5 |
| 3 | OOP | 1 |
| 4 | Programming 1 | ولا حاجة |
| 5 | Discrete Math | ولا حاجة |
أول حل بييجي في دماغك: لف على المواد، وأول مادة كل شروطها خلصت خدها، وارجع لف من الأول.
بص عليه وهو شغال. الأحمر = لسه مش جاهزة، والأخضر = جاهزة، والـ teal = خلصت:
الترتيب صح، بس شوف الـ waste: كل لفة بتبدأ من الصفر وتلف على الـ edges تاني. ده ممكن يوصل لـ V × V × E، يعني 2000 مادة و 5000 شرط = حوالي 20 مليار عملية. Kahn هيعملها في O(V + E)، يعني حوالي 7000.
طب إزاي تعرف من كلام المسألة إنها محتاجة أنهي أداة من التلاتة؟ ده الجزء الجاي.
إزاي تعرف الأداة من المسألة
أول 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، مش العكس.
- in-degree: عدد الأسهم الداخلة في الـ node. في مسائل الترتيب معناه "مستنية كام حاجة". Algorithms (رقم 2) الـ in-degree بتاعها 2، لأنها مستنية 0 و 5.
- out-degree: عدد الأسهم الخارجة منها.
- directed cycle: تمشي مع الأسهم وترجع لنفس الـ node.
- DAG (Directed Acyclic Graph): مفيهوش ولا cycle. الـ topological order موجود لو وبس لو الـ graph كان DAG.
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 بتعدّ الأسهم الداخلة:
- list لكل node. ليه مش
new Array(n).fill([])؟ عشانfill([])بيحط نفس الـ array في كل الخانات، فأي push بيظهر في الكل. - الكل بيبدأ مش مستني حاجة.
fill(0)هنا آمن لأن الصفر مش object. - اقرا المسألة كويس:
[u, v]معناه سهم منuلـvولا العكس؟ دي أكتر حتة الناس بتغلط فيها. - ده الفرق الوحيد عن الـ undirected: مفيش
adj[v].push(u). لو ضفته، هتقدر تمشي عكس السهم وكل حاجة هتبوظ. 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 بتاعها صفر مش مستنية حاجة، فممكن تيجي دلوقتي:
- ابدأ بالجاهزين: كل node الـ in-degree بتاعها صفر تدخل الـ queue.
- خلّص واحدة: طلّعها وحطها في الترتيب، وكل سهم
u → vخارج منها يعملindeg[v]--. - جاهز جديد: لو
indeg[v]بقى صفر،vتدخل الـ queue. - في الآخر: الترتيب فيه
nnode؟ تمام. أقل؟ يبقى فيه nodes محبوسة في cycle.
الـ queue هنا نفس اللي في قالب الـ BFS: array عادية ومعاها head، من غير shift().
- الـ nodes من
0لـn - 1، و[u, v]معناهuقبلv. لو المسألة كاتبة الشرط بالعكس، اقلبه وإنت بتبني. - البناء اللي لسه شايفينه.
- مش هنستخدم
queue.shift(): بيزحزح كل العناصر، يعني O(n) كل مرة، والحل كله يبقى O(n²). الـheadبيحل ده. - ليه نلف على كل الـ
n؟ ممكن يبقى فيه أكتر من node جاهزة، وممكن مادة مالهاش ولا edge. دي in-degree بتاعها صفر ولازم تدخل الترتيب. <مش<=: لماheadيحصّلlengthيبقى الـ queue فضي، وqueue[queue.length]هيطلعundefined.queue[head++]: اقرا الأول، وبعدين زوّدhead.uخلصت، فكل اللي بعدها مستني حاجة أقل.- ليه
=== 0، ومش محتاجين visited؟ كل edge بينقّص مرة واحدة، فالـindeg[v]بيعدّي على الصفر مرة واحدة بس في حياته. يعني كل node بتدخل الـ queue مرة بالظبط. الـ in-degree هنا هو الـ visited. - أهم سطر. 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 |
- directed: سهم في اتجاه واحد. مش محتاجين in-degree هنا.
- Gray أول ما ندخل: "أنا على الطريق ده دلوقتي". الـ nodes الـ gray في أي لحظة هي بالظبط اللي على الـ call stack.
- Gray = cycle.
vgray يعني فيه طريقv → … → u، والسهمu → vبيقفل الدايرة. بنعمل early return بـtrue. - أبيض؟ ننزل له، ولو لقى cycle نوصّل الـ
trueلفوق. وأسود؟ ولا شرط بيتحقق فبنعدّيه، لأنه اتفتش ومش على الطريق الحالي، فمش ممكن يقفل دايرة. - Black لما نخلص، مش white. لو رجّعته أبيض زي الـ backtracking، كل طريق يوصل له هيفتّشه من الأول، والوقت ممكن يبقى exponential.
- الـ graph ممكن يبقى حتت، والـ cycle ممكن تبقى في حتة الـ DFS الأول ما وصلهاش. زي الـ components: نبدأ من كل node لسه بيضا.
على graph فيه الحالتين: diamond (0 → 1 → 3 و 0 → 2 → 3) و cycle (2 → 4 → 5 → 2):
التعقيد: كل node بيتعمل لها dfs مرة (وهي بيضا)، وكل سهم بنبص عليه مرة: O(V + E).
Maximum call stack size exceeded عند عمق حوالي 10,000 (بيختلف حسب البيئة). Kahn مفيهوش recursion، فهو أأمن في الـ inputs الكبيرة. قول ده في الانترفيو.
post.push(u) جنب color[u] = BLACK، وفي الآخر اعمل post.reverse(): هيطلعلك topological order صح، لأن كل node بتتحط بعد كل اللي بعدها.
عندك أداتين للـ cycle: Kahn و الـ 3 colors. يلا على أول مسألة حقيقية.
مثال محلول 1: Course Schedule
عندك numCourses مادة من 0 لـ numCourses - 1، و list شروط. الشرط [a, b] معناه: عشان تاخد a لازم تكون خلصت b. ينفع تخلص كل المواد؟
الجديد هنا إن المسألة مش بتقولك "graph" خالص. لازم إنت اللي تترجم الشروط لأسهم، وتعرف إن "ينفع؟" معناها "مفيش cycle؟".
- اتجاه السهم:
[a, b]يعنيbالأول، فالسهمb → a. الترتيب في الـ pair عكس الترتيب في الوقت، وده trap. - Brute force: جرّب كل ترتيبات المواد:
n!، يعني 10 مواد بس = 3.6 مليون. مستحيل. - الـ key insight: ترتيب موجود ⟺ مفيش cycle. فالمسألة هي "فيه cycle في directed graph؟"، وهنحلها بالـ 3 colors.
- Edge cases: مفيش شروط (true)، مادة شرط لنفسها
[0, 0](false)، مواد ملهاش علاقة ببعض.
- أهم سطر.
bالأول، فالسهمadj[b].push(a). هنا لو قلبته الإجابة هتطلع صح بالصدفة (قلب كل الأسهم بيسيب الـ cycle cycle)، بس في Course Schedule II الترتيب هيطلع مقلوب. اكتبها صح من الأول. 0أبيض،1رمادي،2أسود.- نفس الـ DFS اللي في القالب بالظبط.
- الدالة بتسأل "ينفع؟"، فأول cycle نرجّع
false. خلي بالك من القلب:hasCycleFromبترجّعtrueلما الحاجة وحشة.
| Input | المتوقع | ليه مهمة |
|---|---|---|
| n = 3, [] | true | مفيش أسهم خالص |
| n = 3, [[0,0]] | false | self-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 الشروط).
طب لو المسألة عايزة الترتيب نفسه، مش بس "ينفع ولا لأ"؟
مثال محلول 2: Course Schedule II
نفس المسألة، بس رجّع ترتيب تاخد بيه كل المواد (أي ترتيب صح ينفع). ولو مستحيل، رجّع array فاضية.
الجديد هنا إن المطلوب الترتيب نفسه، فـ Kahn أنسب لأن الترتيب بيطلع منه على طول. وفيه trick صغير: مش محتاجين array اسمها order خالص.
- ليه؟ في قالب
headالعناصر مش بتتمسح. كل node بتدخل الـ queue مرة وتطلع بنفس ترتيب دخولها، فالـqueueنفسها في الآخر هي الترتيب. - Edge cases: cycle (
[])، مادة واحدة ([0])، مفيش شروط ([0, 1, 2, …]).
- السهم
b → a، وaهي اللي مستنية، فـindeg[a]++. لو كتبتindeg[b]++الترتيب هيطلع مقلوب أو[]غلط. - لو مفيش ولا مادة من غير شروط، الـ queue فاضي والإجابة
[]، وده صح: كل مادة ليها شرط يبقى أكيد فيه cycle. - Kahn بالحرف، من غير
order.push. - في الآخر
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؟". ولما كابل يربط مجموعتين، ندمجهم.
parent[i]= الخطوة الجاية في الطريق للـ leader. والـ leader أبوه هو نفسه:parent[r] === r.find(x): امشي وراparentلحد الـ leader.union(a, b): هات الـ leaders. لو نفس الـ leader، هما أصلًا مع بعض. لو لأ، leader يبقى أبوه الـ leader التاني.
لو رسمت سهم من كل i لـ parent[i] هتلاقي forest: كل مجموعة شجرة والـ leader فوق.
المشكلة: السلسلة الطويلة، وحلّين ليها
لو دمجت بغباء ممكن تطلع سلسلة طولها n، و find ترجع O(n). تحسينين، ومع بعض كل عملية تبقى تقريبًا O(1):
- Union by size: الشجرة الصغيرة تتعلّق تحت الكبيرة. عمق أي node بيزيد بس لما مجموعتها تتدمج في واحدة قدّها أو أكبر، يعني الحجم بيتضاعف، فالعمق عمره ما يعدّي
log₂ n. - Path compression: وإنت راجع من
find، كل node عدّيت عليها تشاور على الـ leader مباشرة. زي ما توصل لعنوان وتكتبه في ورقة عشان المرة الجاية.
مع الاتنين، الـ amortized cost لكل عملية O(α(n))، و α أقل من 5 لأي n هتشوفه. في الانترفيو قول "تقريبًا O(1) amortized".
[0, 1, …, n - 1]: الـ function بتاخد (القيمة، الـ index) وبترجّع الـ index. كل واحد leader لنفسه.size[r]= حجم المجموعة. صح عند الـ leaders بس، والباقي محدش بيبص عليه.count= عدد المجموعات، وبينقص مع كل دمج. ده عدد الـ connected components ببلاش.- السطر ده بيعمل حاجتين: بيجيب الـ leader بالـ recursion، وبيحطه في
parent[x]وهو راجع. وكل نداء في السلسلة بيعمل كده، فكل اللي في الطريق بيتربط بالـ leader. ده الـ path compression. parent[x]مشx: بعد السطر اللي فوق،parent[x]هو الـ leader.- دايمًا اشتغل على الـ leaders.
union(a, b)معناها "ادمج مجموعةaمع مجموعةb"، فلازم الـ roots الأول. - نفس الـ leader؟ مفيش دمج. والـ
falseدي مفيدة: معناها "الـ edge ده بيقفل cycle". - swap عشان
raيبقى الأكبر، والـ root الصغير يتعلّق تحته. مشparent[b] = a: ده بيربط عنصر بعنصر، ولوbمش leader هيقطعه من مجموعته. - الـ 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
عندك n data center ومصفوفة isConnected: لو isConnected[i][j] = 1 فيه كابل مباشر بين i و j. المنطقة = مجموعة بتوصل لبعض مباشرة أو من خلال غيرها. كام منطقة؟
دي نفس المسألة اللي حليناها بالـ DFS في فصل الأساسيات، واللي بتيجي في الـ online assessments باسم "قسّم شبكة الـ data centers لمناطق". الجديد هنا إن الأداة اتغيرت: بدل ما نمشي في الـ graph، كل 1 في المصفوفة بقى union، والإجابة هي count ببلاش.
- الترجمة: كل 1 = edge، والمنطقة = connected component.
- الخطة: ابدأ بـ
nمنطقة، واعملunionلكل 1. كل دمج ناجح بيقلّل واحد. - توفير: المصفوفة متماثلة والقطر كله 1، فكفاية النص اللي فوق القطر:
j > i.
- في الأول
count = n: كل data center منطقة لوحده. - ليه
j = i + 1مش0؟[i][j]و[j][i]نفس الكابل، والقطر معناه "موصّل بنفسه". من 0 هتعملunionمرتين على الفاضي. - لو الاتنين أصلًا منطقة واحدة (زي
[1][3]: اتربطوا عن طريق 0)، الـunionبيرجّعfalseوcountما بيتغيرش. nناقص الدمجات الناجحة، والـ DSU بيعدّها لوحده.
الصف اللي بنلف عليه أزرق، والـ 1 اللي بنعالجه أصفر، والـ forest تحت بيتغير مع كل دمج:
| Input | المتوقع | ليه مهمة |
|---|---|---|
| [[1]] | 1 | data 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
كان عندك tree فيها n node من 1 لـ n (connected ومفيهاش cycle)، وحد ضاف edge زيادة، فبقوا n edge. رجّع edge لو شلته ترجع tree، ولو فيه أكتر من إجابة رجّع آخر واحد في الـ input.
الجديد هنا إن الـ false اللي union بيرجّعه هو الإجابة نفسها: edge طرفيه أصلًا متوصلين = edge بيقفل cycle.
- Brute force: شيل كل edge من الآخر واعمل DFS تتأكد إن الباقي tree:
O(n²). - الـ key insight: ضيف الـ edges بالترتيب في الـ DSU. أول edge طرفيه في نفس المجموعة يبقى فيه طريق بينهم من غيره، فهو بيقفل الـ cycle الوحيدة.
- ليه هو "آخر واحد"؟ كل edges الـ cycle اللي قبله اتضافوا عادي، وهو اللي قفل الدايرة، يعني هو آخر واحد فيهم في الـ input.
- tree بـ
nnode فيهاn - 1edge، وواحد زيادة يبقواn. فعدد الـ nodes = عدد الـ edges. - Off-by-one كلاسيكي. الـ nodes من
1لـn. معnew DSU(n)،parent[n]هيبقىundefined، وfind(n)هتناديfind(undefined)لحد ما الـ stack يضرب. فبنعملn + 1ونسيب الخانة 0. - أول
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
عندك n كمبيوتر من 0، و list كابلات. تقدر تفك أي كابل وتوصّله بين أي جهازين. أقل عدد نقلات عشان الكل يوصل لبعض؟ ولو مستحيل رجّع -1.
الجديد هنا إن بنستخدم الحاجتين مع بعض: count بيقولنا محتاجين كام نقلة، والـ false بيقولنا عندنا كام كابل زيادة.
- الاستحالة:
nجهاز محتاجينn - 1كابل على الأقل. أقل من كده؟-1. - العدّ: لو فيه
kمجموعة، كل نقلة بتربط اتنين، فمحتاجينk - 1. - الكابلات كفاية؟ المجموعات محتاجة
n - kكابل عشان تفضل متوصلة، والباقي زيادة. ولو الكابلات≥ n - 1يبقى الزيادة≥ k - 1، يعني دايمًا كفاية.
- كل كابل بيقلّل المجموعات واحد بالكتير، فمن
nلواحدة محتاجn - 1. و<مش<=:n - 1بالظبط ممكن يكفّوا. - اللي
unionبتاعه رجّعfalseده الكابل الزيادة اللي هننقله. - كله متوصل؟
count = 1والإجابة 0.
| Input | المتوقع | ليه مهمة |
|---|---|---|
| n = 1, [] | 0 | جهاز واحد |
| n = 4, [[0,1],[0,2],[1,2]] | 1 | 3 كابلات = n - 1 بالظبط، وواحد زيادة يتنقل لـ 3 |
| n = 6, [[0,1],[0,2],[0,3],[1,2]] | -1 | 4 أقل من 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 لسه ما طلعتش، نحدّثها عادي.
ليه الـ node اللي بتطلع مسافتها final؟ لو u هي الأقرب من اللي لسه ما خلصوش بمسافة d، أي طريق تاني ليها لازم يعدّي على node لسه ما خلصتش ومسافتها ≥ d، وبعدها الأوزان مش سالبة فالطريق مش هيقصر. يعني مفيش أقل من d.
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:
- شجرة متخزّنة في array: الـ root في
a[0]، وكل أب أصغر من ولاده، فالأصغر دايمًا فيa[0]. العنصر[dist, node]والمقارنة بـ[0]. - الجديد بيتحط في الآخر. أبو الخانة
iهو(i - 1) >> 1، يعنيMath.floor((i - 1) / 2)، والولاد2i + 1و2i + 2. - طول ما الأب أكبر، بدّلهم واطلع. العمق
log n، فالـ push بـO(log n). - بنحفظ الـ root عشان نرجّعه، ونحط آخر عنصر مكانه. ولو الـ heap كان فيه عنصر واحد، خلاص فضي.
- نبدّل مع أصغر ابن وننزل، عشان اللي يطلع فوق يبقى أصغر من أخوه كمان. برضه
O(log n).
ودلوقتي Dijkstra نفسه. حط عينك على السطر 9:
- كل عنصر في
adj[u]هو[v, w]، ولازم كل الأوزان≥ 0. - ليه
Infinityمش-1؟ الشغل كله مقارنات<، وأي طريق حقيقي أصغر منInfinityتلقائي. ولو فضلتInfinityفي الآخر، الـ node دي مش reachable. - الترتيب جوه الـ pair مهم:
[dist, node]، لأن الـ heap بيقارن بأول خانة. لو قلبتهم، هيطلّع أصغر رقم node والحل يبوظ من غير error. - طلّع الأقرب: ده الـ greedy step.
- Lazy deletion. لما بنلاقي طريق أقصر لـ
vمش بنعدّل الـ entry القديمة، بنزوّد واحدة جديدة. القديمة لما تطلع هتبقىd > dist[u]، يعني stale، فنرميها. وليه>مش>=؟ الـ entry الصح بتطلع وd === dist[u]. مع>=، أول pop[0, src]نفسه هيترمي، وكل المسافات تفضلInfinity. - ده الـ relaxation: طريق عن طريق
uأقصر من اللي نعرفه؟ و<مش<=: طريق بنفس الطول مش هيغيّر حاجة. - نحدّث وندخّل entry جديدة. لو
vليها entry قديمة، بقت stale وسطر 9 هيرميها.
الرقم تحت كل node هو أقصر مسافة معروفة، والـ heap مرسوم مترتب: أول واحد هو اللي هيطلع، وكل entry (المسافة، الـ node). الـ stale بالأحمر، والـ edges المتلونة هي أقصر الطرق:
| BFS | Dijkstra | |
|---|---|---|
| الـ edges | من غير أوزان | أوزان مختلفة، ≥ 0 |
| الطابور | queue: FIFO | min-heap: الأقرب الأول |
| المسافة بتتقفل إمتى | لما الـ node تدخل (visited on push) | لما الـ node تطلع من الـ heap |
| الـ node بتدخل كام مرة | مرة واحدة | ممكن أكتر، والزيادة stale |
| Complexity | O(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
شبكة فيها n جهاز من 1 لـ n. كل [u, v, w] في times معناه إشارة من u بتوصل v بعد w (اتجاه واحد). بعتنا إشارة من k. بعد قد إيه كل الأجهزة توصلها؟ ولو جهاز عمره ما هيوصله حاجة، -1.
الجديد هنا إن الإجابة مش dist نفسها: الإشارة بتمشي في كل الطرق مع بعض، فالكل استلم لما آخر واحد يستلم، يعني max(dist). وكمان الـ graph directed والـ nodes من 1.
- الأداة: أوزان مختلفة ومش سالبة، من بداية واحدة: Dijkstra من
k. - الإجابة:
max(dist[1..n])، ولو فيهInfinityيبقى-1. - Edge cases: جهاز واحد (0)، جهاز مش reachable (-1)، واتجاه الـ edges.
n + 1عشان الـ nodes من1، والخانة 0 مش مستخدمة. أسهل من إنك تطرح 1 من كل رقم.- directed: مفيش
adj[v].push([u, w]). - القالب بالحرف (
d + wمكانnd). - هنا الـ off-by-one بيستخبى. لو بدأت من
i = 0،dist[0] = Infinityفالإجابة هتطلع-1دايمًا. ولوi < n، هتنسى آخر جهاز وممكن يكون هو الأبطأ. و max مش sum، لأن الإشارة بتمشي في كل الطرق في نفس الوقت. - أي جهاز
Infinityيخلّي الـ maxInfinity، فنرجّع-1.
| Input | المتوقع | ليه مهمة |
|---|---|---|
| [], n = 1, k = 1 | 0 | الجهاز اللي بعت هو الوحيد |
| [[1,2,1]], n = 2, k = 2 | -1 | الاتجاه: من 2 مفيش سهم خارج |
| [[1,2,1],[2,3,2],[1,3,4]], n = 3, k = 1 | 3 | المباشر (4) أطول من اللي بيعدّي على 2 |
التعقيد: O((n + E) log n) وقت (E = times.length)، و O(n + E) memory.
طب لو تكلفة الطريق مش مجموع، والـ graph كمان grid؟
مثال محلول 7: Path With Minimum Effort (Dijkstra على grid)
grid ارتفاعات. هتمشي من الشمال فوق لليمين تحت في أربع اتجاهات. مجهود الطريق = أكبر فرق ارتفاع بين خانتين ورا بعض فيه. عايز أقل مجهود.
الجديد هنا إن تكلفة الطريق max مش sum، والـ graph grid. Dijkstra لسه شغال؟ أيوه، لأن الإثبات محتاج حاجة واحدة: التكلفة ما بتقلّش وإنت بتطوّل الطريق، والـ max عمره ما بيقل.
- الـ grid graph: كل خانة node، والجيران بالـ DIRS والـ bounds check زي فصل الـ Grid، ووزن الخطوة = فرق الارتفاع.
- التغيير الوحيد:
Math.max(e, w)مكانd + w. - Early return: أول ما الخانة الأخيرة تطلع من الـ heap، مجهودها final.
- حل تاني: binary search على الإجابة + BFS بالخطوات اللي فرقها ≤ X. برضه مقبول.
- الـ
distهنا 2D، وكل صف array جديدة (نفس فخfill). [effort, r, c]: المجهود الأول لأن الـ heap بيقارن بأول خانة.- نرجّع لما الهدف يطلع مش لما يدخل. وهو داخل ممكن يبقى فيه طريق أحسن لسه ما اتكتشفش. وهو طالع، هو الأقرب من كل اللي فاضل.
- bounds check:
>= Rمش> R، لأن آخر index هوR - 1. - قلب المسألة: الأكبر بين مجهود اللي فات وفرق الخطوة دي، و
Math.absلأن النزول زي الطلوع. - مش هيتنفّذ: الهدف دايمًا 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.
تمرين: فكّر قبل ما تفتح
list معادلات، كل واحدة 4 حروف: يا "x==y" يا "x!=y"، والمتغيرات حروف إنجليزي صغيرة. ينفع تدّي كل حرف رقم، وكل المعادلات تطلع صح؟
تلميح 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 دقيقة على مسألة، ارجع للقالب هنا، وبعدين حاول تاني من غير ما تبص.
- Course Scheduleالمثال المحلول 1. حلها مرة بالـ DFS ومرة بـ Kahn.
- Course Schedule IIKahn بالحرف، وخلي بالك من اتجاه السهم.
- Find Eventual Safe Statesالتلات ألوان بمعنى جديد: الـ node الآمنة هي اللي بقت black.
- Redundant Connectionأول DSU:
unionبيرجّع false يعني cycle. - Make Network Connectedعدّ المجموعات بـ
count، والشرط بتاعn - 1. - Count Unreachable Pairs of Nodesاستخدم
sizeبتاع كل مجموعة، والإجابة ممكن تبقى كبيرة. - Satisfiability of Equality Equationsالتمرين اللي فوق: DSU على حروف، ولفتين.
- Accounts MergeDSU على strings: حوّل كل إيميل لرقم بـ Map الأول.
- Network Delay Timeالمثال المحلول 6: Dijkstra الخام، واكتب الـ MinHeap من دماغك.
- Path with Maximum ProbabilityDijkstra مقلوب: أكبر حاصل ضرب، فالـ heap يبقى max.
- Path With Minimum Effortالمثال المحلول 7: Dijkstra على grid والتكلفة max.
- Cheapest Flights Within K Stopsحد لعدد المحطات، فالـ Dijkstra العادي مش كفاية: BFS بالطبقات أو Bellman-Ford بـ k لفة.
- Min Cost to Connect All Pointsفكرة جديدة اسمها MST: رتّب الـ edges ووصّل بالـ DSU (Kruskal)، أو heap زي Dijkstra (Prim).
- Parallel Courses IIIاختياري: Kahn ومعاه أطول وقت لكل مادة.
وفي الآخر، الفصل كله في صفحة واحدة.
الخلاصة
| المسألة بتقول | الأداة | Complexity |
|---|---|---|
| أقصر طريق، كل خطوة بنفس التمن | BFS | O(V + E) |
| أقصر طريق، أوزان مختلفة ومش سالبة | Dijkstra + min-heap | O((V + E) log V) |
| أوزان سالبة، أو عدد محطات محدود | Bellman-Ford (برا الفصل) | O(V · E) |
| ترتيب بشروط، أو "ينفع تخلص كله؟" | Topological sort: Kahn أو DFS 3 colors | O(V + E) |
| الـ edges بتيجي واحد واحد، "متوصلين؟"، دمج | Union-Find | ≈ O(1) لكل عملية |
| edge زيادة / cycle في undirected graph | Union-Find (union بيرجّع false) | ≈ O(E) |
| عدّ الـ components (graph ثابت) | BFS أو DFS أو Union-Find | O(V + E) |
| grid: جزر، flood fill، أقل خطوات | BFS / DFS على الـ grid | O(R · C) |
الفصل الجاي: Backtracking. الـ DFS اللي استخدمته هنا (انزل، كمّل، ارجع) هو نفسه هيكل الـ backtracking، بس هتمشي في شجرة اختيارات بتبنيها وإنت ماشي. وفاكر "ما ترجّعش الـ node بيضا عشان الوقت ما يبقاش exponential"؟ في الـ backtracking هتعمل كده بالظبط عن قصد، عشان تجرّب كل الطرق. وبعده Greedy هيرجّعلك فكرة Dijkstra: خد أحسن حاجة قدامك دلوقتي، وإمتى ده يبقى صح.
إزاي الـ DFS ده نفسه يجرّب كل الاحتمالات بنظام؟ ده الفصل الجاي.