Problem link ও উৎস
- **Original source:** Classic graph deep-copy exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** traversal + copy map (deep copy of a graph)
- **Basic idea inherited from:** hash maps ([../../05-hashing/](../../05-hashing/README.md)); DFS/BFS traversal ([../dfs.md](../dfs.md), [../bfs.md](../bfs.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা connected undirected graph-এর একটা node দেওয়া আছে (reference হিসেবে)। প্রতিটা node-এ একটা `val` আর একটা `neighbors` list আছে। তোমাকে পুরো graph-টার একটা **deep copy** বানাতে হবে — মানে প্রতিটা node-এর জন্য একটা সম্পূর্ণ নতুন object, আর copy-graph-এর connection-গুলো হুবহু original-এর মতো, কিন্তু কোনো node share করা যাবে না। নতুন graph-এর starting node ফেরত দাও।
```text
original: 1 -- 2 copy: 1' -- 2'
| | | |
4 -- 3 4' -- 3'
(সব node নতুন object, structure এক)
```
### Input ও output {#8-example-input-and-output}
```text
Input : adjacency = [[2,4],[1,3],[2,4],[1,3]] (node i+1-এর প্রতিবেশী)
Output: একটা নতুন graph, structure হুবহু এক, কিন্তু সব node আলাদা object
Input : adjacency = [[]] (একটা node, প্রতিবেশী নেই)
Output: একটাই নতুন node, val 1, খালি neighbors
Edge case (খালি graph): node = None -> None
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা বন্ধুদের network-এর হুবহু নকল তালিকা বানানো ভাবো। প্রতিটা আসল ব্যক্তির জন্য একটা নতুন কার্ড লেখো, আর একটা খাতায় টুকে রাখো "আসল-X → নতুন-কার্ড-X"। এখন আসল-X-এর প্রতিটা বন্ধুর জন্য: খাতায় দেখো তার নতুন কার্ড আছে কিনা — থাকলে সেটাই X-এর কার্ডে বন্ধু হিসেবে জোড়ো; না থাকলে আগে তার কার্ড বানাও। খাতা (map) ছাড়া তুমি একই ব্যক্তির বারবার কার্ড বানাতে, আর বন্ধুত্বের চক্রে চিরকাল ঘুরতে থাকতে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত দুটো: **hash map** ([../../05-hashing/](../../05-hashing/README.md)) আর **graph traversal** ([../dfs.md](../dfs.md), [../bfs.md](../bfs.md))। Traversal দিয়ে প্রতিটা node একবার করে ছুঁই; আর একটা hash map (`old node -> new node`) দিয়ে মনে রাখি কাকে আগেই copy করেছি। এই map-টাই দুটো কাজ একসাথে করে — visited-marker, আর "এই original-এর copy কোনটা" সেটার lookup। নতুন algorithm নয়, চেনা traversal-এর পাশে একটা mapping বইয়ে নেওয়া।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: graph-এ **cycle আছে**, তাই naive recursion অসীম loop করবে — `1 -> 2 -> 1 -> 2 ...`। চাবি হলো প্রতিটা node-কে **প্রথমবার দেখলেই** তার copy বানিয়ে map-এ রেখে দেওয়া, *তারপর* neighbors-এ নামা। তাই যখন পরে আবার একই original-এ পৌঁছাই, map-এ তার copy পেয়ে যাই আর সেটাই reuse করি — নতুন করে বানাই না। এই "create-then-recurse, map first" order-টাই cycle সামলায় আর প্রতিটা node ঠিক একবার copy নিশ্চিত করে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **hash map `old -> new`** — প্রতিটা original node-এর copy কোনটা; visited-marker-ও বটে।
- **DFS recursion** বা **BFS `collections.deque`** — পুরো graph traverse করতে।
- **node objects** — প্রতিটা copy-তে `val` ও `neighbors` list।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
hash map fit করে কারণ মূল প্রশ্ন "এই original node-এর copy আগে বানিয়েছি কি, বানিয়ে থাকলে কোনটা?" — দুটোই O(1) lookup, ঠিক যা map দেয়; আর map-এ থাকা মানেই visited, তাই আলাদা visited set লাগে না। DFS/BFS দুটোই fit করে কারণ deep-copy-র জন্য শুধু প্রতিটা node ও edge একবার ছোঁয়া দরকার — order বা distance এখানে অপ্রাসঙ্গিক, যেকোনো traversal চলে। node object fit করে কারণ আমরা সত্যিকারের নতুন structure বানাচ্ছি, value নয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম (ভুল) সরল চিন্তা: কোনো map ছাড়া recursively প্রতিটা node-এর copy বানিয়ে neighbors-এ নামা।
```text
1) clone(node): একটা new node বানাও
2) node-এর প্রতিটা প্রতিবেশীর জন্য clone(প্রতিবেশী) ডাকো আর new node-এ জোড়ো
3) (কিন্তু কোনো "আগে দেখেছি" নেই)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
map ছাড়া এটা শুধু ধীর নয়, **সম্পূর্ণ ভুল**: graph-এ cycle থাকায় `1 -> 2 -> 1 -> 2 -> ...` অসীম recursion-এ stack overflow করে। আর cycle না থাকলেও একই node একাধিক path দিয়ে পৌঁছানো যায়, ফলে duplicate copies তৈরি হয় আর structure ভেঙে যায়। map যোগ করলে প্রতিটা node ঠিক একবার copy হয়, repeated visit O(1)-এ থেমে যায় — পুরোটা O(V + E)। তাই map বাড়তি optimization নয়, correctness-এর শর্ত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **node-টা create করো আর map-এ রাখো recurse করার আগে।** তাহলে একটা node তার নিজের cycle দিয়ে ফিরে এলে map-এ ইতিমধ্যেই তার copy আছে — অসীম loop থামে, আর কোনো node দুবার copy হয় না। এই একটাই order-নিয়ম পুরো problem-টাকে নিরাপদ করে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা map `old -> new` রাখো। `clone(node)`: যদি `node` map-এ থাকে, তার copy ফেরত দাও (base case, cycle থামায়)। নাহলে একটা নতুন node বানাও, *সঙ্গে সঙ্গে* `map[node] = new` বসাও, তারপর `node`-এর প্রতিটা প্রতিবেশীর জন্য `clone(প্রতিবেশী)` ডেকে `new.neighbors`-এ জোড়ো। শেষে `new` ফেরত। প্রতিটা node ও edge একবার → O(V + E)। BFS version-এ একই map, deque দিয়ে level-by-level।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "শুধু recurse করে copy বানাব" না ভেবে ভাবো "প্রতিটা original-এর copy কোথায়, সেটা একটা map-এ মনে রাখব — আর copy-টা বানাব recurse করার আগেই, যাতে cycle ফিরে এলে map-ই তাকে থামায়।" Traversal-এর পাশে একটা lookup-table বইয়ে নেওয়াই এখানে আসল কৌশল।
### ছবিতে বোঝা {#7-visual-explanation}
`1 -- 2`, `1 -- 4`, `2 -- 3`, `3 -- 4` (4-চক্র) দিয়ে DFS clone:
```text
original: DFS(1):
1 -- 2 map = {1:1'}
| | DFS(2): map={1:1',2:2'}
4 -- 3 DFS(1)? map-এ আছে -> 1' reuse (cycle থামল)
DFS(3): map={1:1',2:2',3:3'}
DFS(2)? map-এ আছে -> 2' reuse
DFS(4): map={1:1',2:2',3:3',4:4'}
DFS(1)? map-এ আছে -> 1'
DFS(3)? map-এ আছে -> 3'
ফল: 1'--2', 1'--4', 2'--3', 3'--4' (সব নতুন object)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`adjacency = [[2],[1]]` (দুই node, 1 -- 2) দিয়ে DFS:
1. `clone(1)`: map খালি, তাই `1'` বানাই, `map = {1: 1'}`।
2. 1-এর প্রতিবেশী `2` → `clone(2)`: map-এ নেই, `2'` বানাই, `map = {1:1', 2:2'}`।
3. 2-এর প্রতিবেশী `1` → `clone(1)`: map-এ আছে → `1'` ফেরত (cycle থামল)। `2'.neighbors = [1']`।
4. `clone(2)` শেষ, `2'` ফেরত। `1'.neighbors = [2']`। `clone(1)` শেষ, `1'` ফেরত। ফল: `1' -- 2'`, দুটোই নতুন object।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
class Node:
def __init__(self, val, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph_dfs(node):
if node is None:
return None
old_to_new = {} # old node -> new node (visited-ও)
def dfs(cur):
if cur in old_to_new: # আগে copy করেছি -> reuse (cycle থামে)
return old_to_new[cur]
copy = Node(cur.val)
old_to_new[cur] = copy # recurse করার আগেই map-এ রাখি
for nb in cur.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)
def clone_graph_bfs(node):
if node is None:
return None
old_to_new = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nb in cur.neighbors:
if nb not in old_to_new: # প্রথমবার দেখা -> copy বানাও, enqueue
old_to_new[nb] = Node(nb.val)
q.append(nb)
old_to_new[cur].neighbors.append(old_to_new[nb])
return old_to_new[node]
def build(adjacency):
# adjacency[i] = node (i+1)-এর প্রতিবেশীর val list; helper for tests
if not adjacency:
return None
nodes = {i + 1: Node(i + 1) for i in range(len(adjacency))}
for i, nbrs in enumerate(adjacency):
nodes[i + 1].neighbors = [nodes[v] for v in nbrs]
return nodes[1]
def to_adjacency(node):
# clone যাচাইয়ের জন্য graph -> adjacency list (BFS দিয়ে)
if node is None:
return []
seen = {node.val: node}
q = deque([node])
while q:
cur = q.popleft()
for nb in cur.neighbors:
if nb.val not in seen:
seen[nb.val] = nb
q.append(nb)
return [[nb.val for nb in seen[v].neighbors] for v in sorted(seen)]
# ---- tests ----
adj = [[2, 4], [1, 3], [2, 4], [1, 3]]
for cloner in (clone_graph_dfs, clone_graph_bfs):
original = build(adj)
copied = cloner(original)
# structure এক
assert to_adjacency(copied) == adj
# কিন্তু object আলাদা (deep copy, share করা নয়)
assert copied is not original
assert copied.neighbors[0] is not original.neighbors[0]
assert clone_graph_dfs(None) is None
single = clone_graph_dfs(build([[]]))
assert single.val == 1 and single.neighbors == []
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `class Node` — প্রতিটা node-এ `val` ও `neighbors` list, LeetCode-এর signature-এর মতো।
- `old_to_new = {}` — original node থেকে তার copy-র map; map-এ থাকা মানেই visited।
- `if cur in old_to_new: return old_to_new[cur]` — DFS base case; আগে-copy-করা node ফিরে এলে reuse, cycle থামে।
- `old_to_new[cur] = copy` — **recurse করার আগে** map-এ বসানো, এটাই cycle-safety-র চাবি।
- BFS-এ `if nb not in old_to_new:` — প্রথমবার দেখা প্রতিবেশীর copy বানিয়ে enqueue; তারপর সবসময় edge জোড়া।
- `copy.neighbors.append(dfs(nb))` / `old_to_new[cur].neighbors.append(...)` — copy-graph-এ edge পুনর্নির্মাণ।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
দুই cloner-এই: `build(adj)` original graph বানায়, `cloner` deep copy করে। `to_adjacency(copied) == adj` দেখায় structure হুবহু এক। `copied is not original` আর `copied.neighbors[0] is not original.neighbors[0]` দেখায় object গুলো আলাদা — সত্যিকারের deep copy, কোনো node share করা হয়নি। `None` graph → `None`। single node → val 1, খালি neighbors। সব assert pass, শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class GraphNode {
constructor(val, neighbors = []) { this.val = val; this.neighbors = neighbors; }
}
function cloneGraphDFS(node) {
if (node === null) return null;
const oldToNew = new Map(); // old node -> new node (visited-ও)
const dfs = (cur) => {
if (oldToNew.has(cur)) return oldToNew.get(cur); // আগে copy করেছি → reuse (cycle থামে)
const copy = new GraphNode(cur.val);
oldToNew.set(cur, copy); // recurse করার আগেই map-এ রাখি
for (const nb of cur.neighbors) copy.neighbors.push(dfs(nb));
return copy;
};
return dfs(node);
}
function cloneGraphBFS(node) {
if (node === null) return null;
const oldToNew = new Map();
oldToNew.set(node, new GraphNode(node.val));
const q = [node]; let head = 0;
while (head < q.length) {
const cur = q[head++];
for (const nb of cur.neighbors) {
if (!oldToNew.has(nb)) { // প্রথমবার দেখা → copy বানাও, enqueue
oldToNew.set(nb, new GraphNode(nb.val));
q.push(nb);
}
oldToNew.get(cur).neighbors.push(oldToNew.get(nb));
}
}
return oldToNew.get(node);
}
// helper: adjacency[i] = node (i+1)-এর প্রতিবেশীর val list
function build(adjacency) {
if (!adjacency || adjacency.length === 0) return null;
const nodes = new Map();
for (let i = 0; i < adjacency.length; i++) nodes.set(i + 1, new GraphNode(i + 1));
for (let i = 0; i < adjacency.length; i++) {
nodes.get(i + 1).neighbors = adjacency[i].map((v) => nodes.get(v));
}
return nodes.get(1);
}
// clone যাচাইয়ের জন্য graph -> adjacency list (BFS দিয়ে)
function toAdjacency(node) {
if (node === null) return [];
const seen = new Map([[node.val, node]]);
const q = [node]; let head = 0;
while (head < q.length) {
const cur = q[head++];
for (const nb of cur.neighbors) {
if (!seen.has(nb.val)) { seen.set(nb.val, nb); q.push(nb); }
}
}
return [...seen.keys()].sort((a, b) => a - b).map((v) => seen.get(v).neighbors.map((nb) => nb.val));
}
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// ---- test cases ----
const adj = [[2, 4], [1, 3], [2, 4], [1, 3]];
for (const cloner of [cloneGraphDFS, cloneGraphBFS]) {
const original = build(adj);
const copied = cloner(original);
assert(eq(toAdjacency(copied), adj), "structure এক");
assert(copied !== original, "deep copy, root আলাদা");
assert(copied.neighbors[0] !== original.neighbors[0], "neighbor আলাদা object");
}
assert(cloneGraphDFS(null) === null, "null graph");
const single = cloneGraphDFS(build([[]]));
assert(single.val === 1 && single.neighbors.length === 0, "একা node");
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এর dict-এ node-object key হিসেবে রাখা যায়; JS-এ সাধারণ object key string-এ রূপান্তরিত হয়, তাই **`Map` ব্যবহার করা জরুরি** — `Map` আসল object-reference-কে key হিসেবে রাখে (`val` নয়), যা duplicate-val graph-এও সঠিক। create-before-recurse order (`oldToNew.set` আগে, তারপর neighbors loop) cycle থামায়, ঠিক Python version-এর মতো। `!==` reference-অসমতা যাচাই করে deep copy নিশ্চিত করে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
class GraphNode {
val: number;
neighbors: GraphNode[];
constructor(val: number, neighbors: GraphNode[] = []) { this.val = val; this.neighbors = neighbors; }
}
function cloneGraphDFS(node: GraphNode | null): GraphNode | null {
if (node === null) return null;
const oldToNew = new Map