Graphs — Problem Tracker¶
এই folder টা graphs-এর practice problem গুলো track করে। প্রতিটা problem-এর জন্য নিজের একটা note file থাকবে (Note file column-এ নাম দেওয়া), যেটা ../../templates/ds-problem-note-template.md-এর 24-section template দিয়ে লেখা — analogy, pattern, thinking tweak, dry run, complexity, mistakes, আর বাকি সব। List টা easy থেকে hard-এ সাজানো আর এমনভাবে group করা যাতে mixing শুরুর আগে প্রতিটা algorithm (BFS → DFS → topo sort → Dijkstra) একগুচ্ছ করে problem পায়।
এই tracker কীভাবে ব্যবহার করবে:
- Link দিয়ে official statement টা পড়ো (মূল
../README.md-এর practice list-এও আছে)। - Code করার আগে জোরে বলো: আমার nodes কী, edges কী, কোন algorithm আর কেন। এই modeling বাক্যটাই পুরো repo-র সবচেয়ে interview-মূল্যবান অভ্যাস।
- কিছু দেখার আগে অন্তত 25 মিনিট attempt করো।
- Note file টা বানাও, template ভরো, Status-কে
solvedকরো (বাrevisit)।
Status values: planned → attempted → solved / revisit।
Tracker¶
| # | Problem | Difficulty | Source | Pattern | Inherits from | Note file | Status |
|---|---|---|---|---|---|---|---|
| 1 | Find Center of Star Graph | Easy | LeetCode 1791 | Representation warm-up | 09 adjacency basics |
001-find-center-of-star-graph.md | planned |
| 2 | Find if Path Exists in Graph | Easy | LeetCode 1971 | Reachability | 04-stack-and-queue queue |
002-find-if-path-exists.md | planned |
| 3 | Flood Fill | Easy | LeetCode 733 | DFS on grid | 06-recursion-and-backtracking |
003-flood-fill.md | planned |
| 4 | Number of Islands | Medium | LeetCode 200 | Components on grid | 09 flood fill (#3) |
004-number-of-islands.md | planned |
| 5 | Max Area of Island | Medium | LeetCode 695 | Components + size counting | 09 islands (#4) |
005-max-area-of-island.md | planned |
| 6 | Number of Provinces | Medium | LeetCode 547 | Components (matrix input) | 09 components; পরে আবার করো 10-disjoint-set-union দিয়ে |
006-number-of-provinces.md | planned |
| 7 | Building Roads | Easy | CSES task 1666 | Components, CP scale | 09 components |
007-building-roads.md | planned |
| 8 | Rotting Oranges | Medium | LeetCode 994 | Multi-source BFS | 04-stack-and-queue queue |
008-rotting-oranges.md | planned |
| 9 | 01 Matrix | Medium | LeetCode 542 | Multi-source BFS | 09 rotting oranges (#8) |
009-01-matrix.md | planned |
| 10 | Labyrinth | Medium | CSES task 1193 | Grid BFS + path reconstruction | 09 BFS levels |
010-labyrinth.md | planned |
| 11 | Is Graph Bipartite? | Medium | LeetCode 785 | BFS/DFS two-coloring | 09 BFS levels |
011-is-graph-bipartite.md | planned |
| 12 | Building Teams | Medium | CSES task 1668 | Bipartite coloring, CP scale | 09 bipartite (#11) |
012-building-teams.md | planned |
| 13 | Clone Graph | Medium | LeetCode 133 | Traversal + copy map | 05-hashing maps |
013-clone-graph.md | planned |
| 14 | Pacific Atlantic Water Flow | Medium | LeetCode 417 | Reverse flood from borders | 09 flood fill (#3) |
014-pacific-atlantic.md | planned |
| 15 | Course Schedule | Medium | LeetCode 207 | Cycle detection (directed) | 06-recursion-and-backtracking |
015-course-schedule.md | planned |
| 16 | Course Schedule II | Medium | LeetCode 210 | Topological sort (Kahn) | 09 course schedule (#15) |
016-course-schedule-ii.md | planned |
| 17 | Course Schedule (CSES) | Medium | CSES task 1679 | Topo sort, CP scale | 09 Kahn (#16) |
017-course-schedule-cses.md | planned |
| 18 | Network Delay Time | Medium | LeetCode 743 | Dijkstra | 08-heap-priority-queue heap |
018-network-delay-time.md | planned |
| 19 | Shortest Routes I | Medium | CSES task 1671 | Dijkstra, CP scale | 09 Dijkstra (#18) |
019-shortest-routes-i.md | planned |
| 20 | Path With Minimum Effort | Medium | LeetCode 1631 | Minimax Dijkstra on grid | 09 Dijkstra (#18) |
020-path-with-minimum-effort.md | planned |
| 21 | Word Ladder | Hard | LeetCode 127 | BFS on implicit graph | 09 BFS + 05-hashing |
021-word-ladder.md | planned |
| 22 | Cheapest Flights Within K Stops | Hard | LeetCode 787 | Bellman-Ford passes | 09 shortest-path table |
022-cheapest-flights-k-stops.md | planned |
| 23 | Bus Routes | Hard | LeetCode 815 | BFS on transformed graph | 09 modeling habit |
023-bus-routes.md | planned |
| 24 | Alien Dictionary | Hard | LeetCode 269 | Build constraints + topo sort | 09 Kahn (#16) |
024-alien-dictionary.md | planned |
| 25 | Swim in Rising Water | Hard | LeetCode 778 | Minimax Dijkstra | 09 minimax (#20); পরে আবার করো 10-disjoint-set-union দিয়ে |
025-swim-in-rising-water.md | planned |
Suggested milestones (পরামর্শমতো মাইলফলক)¶
-
7-এর পর: components আর flood fill reflex হয়ে গেছে; না ভেবেই grid ↔ graph convert করতে পারো।¶
-
14-এর পর: BFS layers, multi-source seeding, আর reverse flooding — সব মিলে একটাই tool মনে হয়।¶
-
17-এর পর: directed graph-এ cycle detect আর ordering produce — দুটোই ঠান্ডা মাথায় পারো।¶
-
20-এর পর: Dijkstra plus তার minimax variant — "queue → deque → heap" বলো আর সত্যিই বোঝাও।¶
-
25-এর পর: অদ্ভুত statements-কে (buses, alien letters, rising water) graph হিসেবে model করতে পারো। এগিয়ে যাও
../../10-disjoint-set-union/-এ, তারপর #6 আর #25-এ ফিরে এসে DSU দিয়ে দ্বিতীয় solution লেখো — দুই solution-এর তুলনাতেই সবচেয়ে গভীর শেখাটা লুকিয়ে আছে।¶