အခန်း ၁၇ - Graphs

ရှေ့ အခန်းတွေ မှာ tree တွေကို လေ့လာခဲ့ပါတယ်။ node တွေ parent → child ဆက်စပ်ပြီး၊ အပေါ်ဆုံးမှာ root ၁ ခု၊ cycle မရှိတဲ့ structure ပါ။ ဒါပေမယ့် real-world relationship အများစုက tree လောက် သေသပ် မှု မရှိပါဘူး။ Facebook မှာ A က B ရဲ့ သူငယ်ချင်း၊ B က C ရဲ့၊ C က ပြန်ပြီး A ရဲ့ သူငယ်ချင်း ဖြစ်နေတာမျိုး ၊ မြို့တွေကြားက လမ်းတွေ က တစ်ခုကို တစ်ခုက မှီခို နေတာ မျိုးပေါ့။

"ဘယ်ဟာက ဘယ်ဟာနဲ့ ဆက်စပ်နေလဲ" ဆိုတဲ့ relationship တွေကို model လုပ်ဖို့ — Graph ကို သုံးပါတယ်။ တကယ်တော့ tree ဆိုတာ graph ရဲ့ အထူး အမျိုးအစား (cycle မရှိ၊ ဆက်စပ်နေတဲ့ graph) တစ်မျိုးပါပဲ။ Graph က တော့ Node အခြင်းခြင်း ဆက်သွယ်မှု တွေ ကို ရှိပါတယ်။

Graph ဆိုတာ ဘာလဲ — Vertex နဲ့ Edge

Array, linked list တွေက sequential (တစ်ခုပြီးတစ်ခု) ဖြစ်ပြီး၊ tree တွေက hierarchical (parent → child) ဖြစ်တယ်။ Graph ကတော့ non-linear data structure တစ်မျိုးပါ။ vertex တွေကြား relationship ကို ဘယ်လိုပုံစံနဲ့မဆို ကိုယ်စားပြုလို့ ရတယ်။ Graph ဆိုတာ အပိုင်း ၂ ခုနဲ့ ဖွဲ့စည်းထားတာ ဖြစ်ပါတယ်။

• Vertex (node): အချက်တစ်ခု — ဥပမာ user တစ်ဦး၊ မြို့တစ်မြို့၊ task တစ်ခု။
• Edge: vertex ၂ ခုကြား ဆက်သွယ်မှု (connection) — ဥပမာ "သူငယ်ချင်း ဖြစ်တယ်"၊ "လမ်း ရှိတယ်"၊ "မှီခိုတယ်"။

graph TD
    A((Node A)) ---|Edge| B((Node B))
    A ---|Edge| C((Node C))
    B ---|Edge| D((Node D))
    C ---|Edge| D

• Node/Vertex: A, B, C, D
• Edge: A–B, A–C, B–D, C–D

အပေါ်က ဥပမာမှာ — user ၄ ဦး (A, B, C, D) ရှိပြီး၊ မျဉ်း (edge) တစ်ခုစီက "သူငယ်ချင်း ဖြစ်တယ်" ကို ဆိုလိုပါတယ်။ Tree နဲ့ မတူတာက graph မှာ root မရှိတာပါ။

ဘယ် vertex က မဆို စလို့ ရ၊ cycle (A–B–D–C–A လို cycle) ရှိလို့ ရပါတယ်။

Tree vs Graph

အခန်း ၁၃ မှာ ပြောခဲ့တာ ပြန်သတိရစေချင်ပါတယ် — tree ဆိုတာ graph ရဲ့ အထူး အမျိုးအစား တစ်မျိုးပါ။ Tree တိုင်းဟာ graph တစ်ခု ဖြစ်ပေမယ့် graph တိုင်းက tree မဖြစ်ပါ။ တကယ်တော့ Linked List, Tree, Heap အကုန်လုံးက graph ရဲ့ အထူးပုံစံ တွေပါပဲ။

အခြေခံချုပ် — graph မှာ rule နည်းလေ၊ ပို general လေ။ Tree က rule တွေ ပိုများပြီး (root ၁ ခု, cycle မရှိ, parent ၁ ခု) structure ပို သေသပ်တယ်။ Rule တွေ တိုးတာက graph ကို ပိုပြီး ထိန်းချုပ်လွယ်စေပြီး၊ algorithm တွေကိုလည်း ရိုးရှင်းစေတယ်။ ဥပမာ — tree မှာ cycle မရှိလို့ traversal က ပို ရိုးရှင်းတယ်။

Graph အမျိုးအစားများ

Directed vs Undirected

• Undirected graph — edge က ၂ ဖက်စလုံး သွားလို့ ရ။ "A က B ရဲ့ သူငယ်ချင်း" ဆို B ကလည်း A ရဲ့ သူငယ်ချင်း (Facebook friend)။
• Directed graph — edge မှာ ဦးတည်ချက် (direction) ရှိ။ "A က B ကို follow လုပ်တယ်" ဆို B က A ကို follow လုပ်တာ မဟုတ်သေး (Twitter/Instagram follow)။

graph LR
    subgraph U["Undirected (friend)"]
        AU((A)) --- BU((B))
    end
    subgraph D["Directed (follow)"]
        AD((A)) --> BD((B))
    end

Undirected: A↔B ၂ ဖက် တူ။ Directed: A→B သာ၊ B→A မဟုတ်။

Weighted vs Unweighted (အလေးချိန် ရှိ / မရှိ)

• Unweighted graph — edge က "ဆက်နေသလား / မဆက်ဘူးလား" ပဲ ဆိုလို။
• Weighted graph — edge တစ်ခုစီမှာ တန်ဖိုး (weight) ရှိပါတယ်။ — ဥပမာ မြို့ ၂ မြို့ကြား အကွာအဝေး၊ network link ရဲ့ latency၊ လမ်းကြောင်း ကုန်ကျစရိတ်။

graph TD
    A((A)) ---|5| B((B))
    A ---|8| C((C))
    B ---|2| D((D))
    C ---|3| D

A→B = 5 km, B→D = 2 km ... (edge weight = အကွာအဝေး)

Weighted graph ကို အသုံးချတဲ့ shortest-path algorithm (Dijkstra စသည်) တွေကို အခန်း ၁၉ မှာ လေ့လာပါမယ်။

Complete vs Incomplete (အပြည့် / မပြည့်)

• Complete graph ($K_n$) — vertex တိုင်းက ကျန် vertex အကုန်နဲ့ ဆက်နေတယ် (မဆက်တဲ့ အိမ်နီးချင်း တစ်ခုမျှ မရှိ)။ vertex n ခုဆိုရင် edge စုစုပေါင်း $n(n-1)/2$ ခု (triangular number) ပါ။ ဥပမာ လူ ၅ ဦးက အချင်းချင်း အကုန် သိကျွမ်းနေတဲ့ အစည်းအဝေး။
• Incomplete graph — အနည်းဆုံး vertex ၂ ခုကြား edge မရှိတဲ့ graph (real-world network တွေက အများအားဖြင့် ဒီအမျိုးအစားပါ)။

$K_n$ notation — $K$ စာလုံးက ဂျာမန် komplett (ပြည့်စုံမှု) ကနေ ဆင်းသက်တယ်လို့ အချို့က ဆိုကြပြီး၊ graph theory ပါဆောင်ရွက်ခဲ့တဲ့ Kazimierz Kuratowski ကို ဂုဏ်ပြုမှ လည်း ပါပါတယ်။ (Wikipedia)

graph TD
    subgraph K3["K3 — 3 edges (triangle)"]
        k3A((A)) --- k3B((B))
        k3A --- k3C((C))
        k3B --- k3C
    end
    subgraph K4["K4 — 6 edges (tetrahedron)"]
        k4A((A)) --- k4B((B))
        k4A --- k4C((C))
        k4A --- k4D((D))
        k4B --- k4C
        k4B --- k4D
        k4C --- k4D
    end
    subgraph K5["K5 — 10 edges (nonplanar)"]
        k5A((A)) --- k5B((B))
        k5A --- k5C((C))
        k5A --- k5D((D))
        k5A --- k5E((E))
        k5B --- k5C
        k5B --- k5D
        k5B --- k5E
        k5C --- k5D
        k5C --- k5E
        k5D --- k5E
    end

Edge အရေအတွက် sequence (triangular numbers):

vertex n ခုစီရင် degree = $n-1$ ဖြစ်ပြီး — $K_n$ ဟာ regular graph (vertex အကုန် degree တူ) တစ်မျိုးပါ။

Geometric အဓိပ္ပာယ် — $K_3$ က triangle၊ $K_4$ က tetrahedron (၃ ဘက် ပုံ) ၏ edge skeleton ဖြစ်ပါတယ်။ $K_1$ မှ $K_4$ အထိ planar (မျဉ်းတွေ မဖြတ်ဘဲ ဆွဲလို့ ရ) ဖြစ်ပေမယ့် — $K_5$ ကစပြီး nonplanar ဖြစ်ပါတယ်။ (Kuratowski's theorem)။

Real-world မှာ complete graph ဟာ ရှားပါတယ် (လူအားလုံး အချင်းချင်း သိဖို့ ဆိုတာ ဖြစ်နိုင်ခြေ နည်း)။ ဒါကြောင့် real-world network တွေက sparse (incomplete) ဖြစ်ပြီး — Adjacency List ကို default အဖြစ် သုံးကြတာပါ။

အရေးကြီး Term များ — Degree, Path, Cycle

• Degree — vertex တစ်ခုမှာ ဆက်နေတဲ့ edge အရေအတွက်။ (Directed graph မှာ — အဝင် edge = in-degree၊ အထွက် edge = out-degree။)
• Path — vertex တစ်ခုကနေ နောက်တစ်ခုသို့ edge တွေ ဆက်ပြီး သွားတဲ့ လမ်းကြောင်း။ ဥပမာ A → B → D က A ကနေ D သို့ path တစ်ခု။
• Cycle — vertex တစ်ခုကနေ ထွက်ပြီး ပြန်ရောက်လာတဲ့ path (A → B → D → C → A)။ Tree မှာ cycle မရှိ၊ graph မှာ ရှိနိုင်။
• Connected Components — တစ်ခုနဲ့ တစ်ခု ဆက်စပ်နေတဲ့ vertex အုပ်စု။ Graph တစ်ခုထဲမှာ တစ်ခုနဲ့ မဆက်တဲ့ အုပ်စု အများကြီး ရှိနိုင်တယ်။

graph LR
    subgraph SG1["Component 1"]
        nA((A)) --- nB((B))
        nA --- nC((C))
    end
    subgraph SG2["Component 2"]
        nE((E)) --- nF((F))
    end
    subgraph SG3["Component 3"]
        nG((G))
    end

G က degree 0 (သီးသန့်)။ → Connected component ၃ ခု: {A,B,C}, {E,F}, {G}

Graph ကို Code ထဲ ဘယ်လို ကိုယ်စားပြုမလဲ

Graph ကို memory ထဲ သိမ်းဖို့ နည်းလမ်း ၂ မျိုး အဓိက ရှိပါတယ် — Adjacency List နဲ့ Adjacency Matrix။ ဘယ်ဟာ ရွေးမလဲ ဆိုတာ graph က dense (edge များ) လား sparse (edge နည်း) လား ပေါ် မူတည်ပါတယ်။

Adjacency List (vertex တစ်ခုစီရဲ့ "အိမ်နီးချင်း" စာရင်း)

vertex တစ်ခုစီအတွက် — သူနဲ့ တိုက်ရိုက် ဆက်နေတဲ့ vertex တွေရဲ့ list ကို သိမ်းတာ။ Real-world မှာ အသုံးအများဆုံး ဖြစ်ပါတယ် (edge နည်းတဲ့ graph အတွက် memory သက်သာ)။

   A: [B, C]
   B: [A, D]
   C: [A, D]
   D: [B, C]

// vertex 0..n-1 အတွက် adjacency list
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

// undirected edge ထည့်တာ — ၂ ဖက်စလုံး
graph.get(u).add(v);
graph.get(v).add(u);

Adjacency Matrix (n × n ဇယား)

matrix[i][j] = 1 ဆို vertex i နဲ့ j ဆက်နေ၊ 0 ဆို မဆက်။ vertex နည်းပြီး edge များတဲ့ (dense) graph အတွက် ရှင်းလင်းပြီး — "i နဲ့ j ဆက်လား" ကို $O(1)$ နဲ့ စစ်လို့ ရတယ်။ ဒါပေမယ့် vertex n ခုဆို နေရာ $O(n^2)$ အမြဲ ယူသည်။

       A  B  C  D
    A [0, 1, 1, 0]
    B [1, 0, 0, 1]
    C [1, 0, 0, 1]
    D [0, 1, 1, 0]

နှိုင်းယှဉ်ချက်

V = vertex အရေအတွက်၊ E = edge အရေအတွက်။ Real-world graph အများစုက sparse (edge နည်း) ဖြစ်လို့ — Adjacency List ကို default အဖြစ် သုံးကြပါတယ်။

Real-world Examples

Graph ဟာ "တစ်ခုနဲ့ တစ်ခု ဆက်စပ်နေတဲ့" data မှန်သမျှမှာ တွေ့ရပါတယ် —

• Users and Friends — social network — user = vertex၊ friendship = undirected edge။ "common friend ရှာ"၊ "သိကျွမ်းခြင်း အဆင့် ၂ ဆင့်" တွေက graph ပြဿနာ။
• City Routes / Maps — မြို့ = vertex၊ လမ်း = weighted edge (အကွာအဝေး)။ GPS route finding က graph ပေါ်မှာ shortest path ရှာတာ။
• Package Dependencies — npm/pip package = vertex၊ "A က B ကို မှီခို" = directed edge။ install order ရှာတာ၊ circular dependency ရှိမရှိ စစ်တာ။
• Permission Graph — role → permission → resource ဆက်စပ်မှု၊ permission inheritance (admin က editor ရဲ့ permission အကုန် ရ)။
• Workflow / State Machine — order status (pending → paid → shipped → delivered) လို state တွေ ကူးပြောင်းမှု — state = vertex၊ transition = directed edge။
• Task Dependency — project task တွေ — "task A ပြီးမှ task B စလို့ ရ" — directed graph ဖြစ်ပြီး၊ scheduling/build system မှာ အသုံးဝင်။

ဒီ pattern တွေ အကုန်လုံး တူပါတယ် — "အရာဝတ္ထု (vertex) တွေနဲ့ သူတို့ကြားက ဆက်စပ်မှု (edge) ကို model လုပ်ပြီး၊ ဆက်စပ်မှု ပေါ်မှာ မေးခွန်း ဖြေ"။ ဒါက graph ရဲ့ အသုံးချပုံ အနှစ်ချုပ်ပါ။

Graph ရဲ့ အားသာချက်များ

• လွတ်လပ်တဲ့ structure — array, linked list, tree တွေလို ကန့်သတ်ချက် (sequential / hierarchy) မရှိဘဲ — ဆက်စပ်မှု ဘယ်လိုပုံစံနဲ့မဆို ကိုယ်စားပြုလို့ ရပါတယ်။
• Real-world problem တွေကို model လုပ်နိုင် — pathfinding, data clustering, network analysis, machine learning စတဲ့ နယ်ပယ် အများအပြားမှာ သင့်တော်။
• ဆက်စပ်မှုကို ရှင်းရှင်းလင်းလင်း မြင်ခွင့် ပေး — vertex–edge သဘောတရားက — ရှုပ်ထွေးတဲ့ relationship တွေကို မြင်သာအောင် ပြင်ပေးတယ်။
• ဘယ် data မဆို graph ဖြစ်နိုင် — item တွေနဲ့ သူတို့ကြားက ဆက်စပ်မှု ပေါ်လာတာနဲ့ — graph တစ်ခု ဖြစ်သွားပါပြီ။

Questions

Graph ကို ပြဿနာ ၄ ခုနဲ့ လေ့လာကြည့်ရအောင်။ ပြဿနာ အများစုက — graph ကို adjacency list အဖြစ် ပြောင်းပြီး၊ vertex တွေကို traversal (DFS/BFS) လုပ်ရင်း visited မှတ်ထားတာ ဖြစ်ပါတယ်။ (DFS/BFS ကို အခန်း ၁၈ မှာ အသေးစိတ် ဆက်လေ့လာမယ် — ဒီမှာ graph အပေါ် ပထမဆုံး အသုံးချ ကြည့်ပါမယ်။)

၁။ Find if Path Exists

vertex n ခု (0..n-1) နဲ့ undirected edge list edges ပေးထားသည်။ source ကနေ destination သို့ path ရှိ/မရှိ ပြန်ပါ။

Example 1:

Input: n = 4, edges = [[0,1],[1,2],[2,0],[3,1]], source = 0, destination = 3
Output: true
   (0 → 1 → 3  လမ်းကြောင်း ရှိသည်)

ရှင်းလင်းချက်

edge list ကို adjacency list အဖြစ် ပြောင်းပြီး — source ကနေ DFS/BFS နဲ့ ဆက်နေသမျှ vertex အကုန် ရောက်ကြည့်ပါတယ်။ destination ကို ရောက်ရင် true။ visited set က — ဆင်းပြီးသား vertex ကို ပြန်မဆင်းအောင် (cycle ကြောင့် infinite loop မဖြစ်အောင်) တားသည်။

• adjacency list ဆောက် (undirected — ၂ ဖက်စလုံး ထည့်)။
• source ကစ DFS — visited မှတ်၊ အိမ်နီးချင်း တစ်ခုစီ ဆက်ဆင်း။
• destination တွေ့ရင် true၊ အကုန် ဆင်းပြီး မတွေ့ရင် false။

Time Complexity: $O(V + E)$ - vertex နဲ့ edge တစ်ခုစီ တစ်ခါစီ ဖြတ်။
Space Complexity: $O(V + E)$ - adjacency list + visited + recursion stack။

Java Solution

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {                // undirected — ၂ ဖက်
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        return dfs(graph, source, destination, new boolean[n]);
    }

    private boolean dfs(List<List<Integer>> graph, int node, int dest, boolean[] visited) {
        if (node == dest) return true;         // ရောက်ပြီ
        visited[node] = true;
        for (int next : graph.get(node)) {
            if (!visited[next] && dfs(graph, next, dest, visited)) return true;
        }
        return false;
    }
}

၂။ Number of Connected Components

vertex n ခု (0..n-1) နဲ့ undirected edge list edges ပေးထားသည်။ connected component (တစ်ခုနဲ့ တစ်ခု ဆက်စပ်နေတဲ့ အုပ်စု) ဘယ်နှ ခု ရှိလဲ ပြန်ပါ။

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
   ({0,1,2}  နဲ့  {3,4}  ၂ အုပ်စု)

ရှင်းလင်းချက်

vertex အကုန်ကို တစ်ခုချင်း ကြည့်ပါတယ် — မ visit ရသေးတဲ့ vertex တစ်ခု တွေ့ရင် → component အသစ် တစ်ခု စပြီ → count တိုး၊ ပြီးတော့ DFS နဲ့ အဲ့ component ထဲက vertex အကုန်ကို visited မှတ်ပစ်။ ဒီနည်းနဲ့ component တစ်ခုစီကို တစ်ခါပဲ ရေတွက်ပါတယ်။

• adjacency list ဆောက်။
• vertex 0..n-1 loop — visited မဟုတ်ရင် count++ + DFS (အုပ်စုတစ်ခုလုံး မှတ်)။

Time Complexity: $O(V + E)$။
Space Complexity: $O(V + E)$ - adjacency list + visited။

Java Solution

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {                 // component အသစ်
                count++;
                dfs(graph, i, visited);        // အုပ်စုတစ်ခုလုံး မှတ်
            }
        }
        return count;
    }

    private void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
        visited[node] = true;
        for (int next : graph.get(node)) {
            if (!visited[next]) dfs(graph, next, visited);
        }
    }
}

၃။ Detect Cycle (Undirected Graph)

vertex n ခု နဲ့ undirected edge list edges ပေးထားသည်။ graph ထဲမှာ cycle ရှိ/မရှိ ပြန်ပါ။

Example 1:

Input: n = 4, edges = [[0,1],[1,2],[2,0],[2,3]]
Output: true
   (0 → 1 → 2 → 0  ဝိုင်းပြန်နေသည်)

ရှင်းလင်းချက်

Undirected graph မှာ — DFS ဆင်းရင်း visited ပြီးသား ဖြစ်တဲ့ vertex တစ်ခုကို ပြန်တွေ့ရင် cycle ဖြစ်နိုင်တယ်။ ဒါပေမယ့် သတိ — A → B ဆင်းပြီး B ကနေ A ကို ပြန်ကြည့်တာက (undirected ဆိုတော့ A–B edge က ၂ ဖက်) cycle မဟုတ်။ ဒါကြောင့် ဘယ်က လာလဲ (parent) ကို မှတ်ထားပြီး — visited ဖြစ်တဲ့ vertex က parent မဟုတ်ရင်မှ cycle ဟု သတ်မှတ်သည်။

• DFS မှာ parent parameter ထည့်။
• အိမ်နီးချင်း next — မ visit ရသေးရင် ဆက်ဆင်း (parent = node)၊ visit ပြီးသား + parent မဟုတ် ဆို → cycle။
• component အကုန်ကို စစ်ဖို့ vertex အကုန် loop။

Time Complexity: $O(V + E)$။
Space Complexity: $O(V + E)$။

Java Solution

class Solution {
    public boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i] && dfs(graph, i, -1, visited)) return true;
        }
        return false;
    }

    private boolean dfs(List<List<Integer>> graph, int node, int parent, boolean[] visited) {
        visited[node] = true;
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                if (dfs(graph, next, node, visited)) return true;
            } else if (next != parent) {       // visited + parent မဟုတ် → cycle
                return true;
            }
        }
        return false;
    }
}

Directed graph ၏ cycle က နည်းနည်း ကွာသည် — "လက်ရှိ DFS လမ်းကြောင်းပေါ်မှာ ရှိနေတဲ့ (in-progress) vertex" ကို ပြန်တွေ့မှ cycle (back-edge) ဟု သတ်မှတ်သည်။ ဒါကို topological sort နဲ့ တွဲပြီး အခန်း ၁၉ မှာ ဆက်လေ့လာပါမယ်။

၄။ Clone Graph

connected undirected graph ရဲ့ node တစ်ခု (node) ပေးထားသည်။ graph တစ်ခုလုံးရဲ့ deep copy (clone) ကို ဆောက်ပြီး ပြန်ပါ။ node တစ်ခုစီမှာ val နဲ့ အိမ်နီးချင်း list neighbors ရှိသည်။

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
   (node 1 ↔ 2,4 ;  node 2 ↔ 1,3 ;  ... တူညီတဲ့ copy အသစ်)

ရှင်းလင်းချက်

ဒီပြဿနာရဲ့ အခက်ဆုံး အပိုင်းက — graph မှာ cycle ရှိလို့၊ node တစ်ခုကို clone လုပ်တိုင်း သူ့ neighbor တွေကိုလည်း clone လုပ်ရင်း အဆုံးမရှိ loop ဖြစ်နိုင်တာ။ ဒါကို ဖြေဖို့ — "မူရင် node → clone node" mapping (HashMap) ကို သိမ်းထားပြီး၊ node တစ်ခုကို တစ်ခါပဲ clone လုပ်ပါတယ်။ ပြန်တွေ့ရင် map ထဲက clone ကို ပြန်သုံး။

• node ကို clone ဆောက်ပြီး map ထဲ ထည့်။
• neighbor တစ်ခုစီ — map ထဲ ရှိရင် ပြန်ယူ၊ မရှိရင် recursion နဲ့ clone ဆောက်။
• map က visited အလုပ်ပါ လုပ်ပေးလို့ — cycle ရှိလည်း loop မဖြစ်။

Time Complexity: $O(V + E)$ - node နဲ့ edge တစ်ခုစီ တစ်ခါ။
Space Complexity: $O(V)$ - map + recursion stack။

Java Solution

// LeetCode ပေးထားတဲ့ Node definition ကို သုံးပါတယ်:
// class Node {
//     public int val;
//     public List<Node> neighbors;
//     public Node(int val) { this.val = val; this.neighbors = new ArrayList<>(); }
// }
class Solution {
    private Map<Node, Node> cloned = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (cloned.containsKey(node)) return cloned.get(node);  // clone ပြီးသား → ပြန်သုံး

        Node copy = new Node(node.val);        // clone အသစ်
        cloned.put(node, copy);                // map ထဲ ထည့် (cycle ကာကွယ်)
        for (Node nb : node.neighbors) {
            copy.neighbors.add(cloneGraph(nb)); // neighbor တွေ clone
        }
        return copy;
    }
}