Chương 9 - Graph

Graph là cấu trúc dữ liệu trừu tượng nhất nhưng cũng phổ biến nhất trong đời thực: bạn bè, đường đi, dependency, … Chương này giới thiệu biểu diễn graph và 6 bài phổ thông về graph. Hai kỹ thuật duyệt BFS, DFS sẽ được đào sâu ở Chương 10 và 11; chương này dùng cả 2 ở mức cơ bản để bạn làm quen.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Thuộc 3 biểu diễn: adjacency list, edge list, matrix.
  • Phân biệt directed vs undirected, weighted vs unweighted.
  • Biết 3 cách traverse: BFS, DFS, Union Find - chọn đúng theo bài.
  • Hỏi clarifying chuẩn: self-loop? multi-edge? disconnected?

Khi nào dùng pattern này?

  • Đề bài cho node + edge (đỉnh + cạnh) - đường đi giữa địa điểm, mạng xã hội, phụ thuộc giữa các task, …
  • Đề bài tuy không nói “graph” nhưng có cấu trúc đồ thị ngầm: dictionary words (Word Ladder), từ điển ngoài hành tinh (Alien Dictionary), …
  • Cần kiểm tra: có đường đi, có chu trình, đường đi ngắn nhất, 2-coloring, connected components.

3 câu hỏi trước khi code: 1. Hướng / vô hướng? Directed cần cân nhắc thêm chu trình. 2. Có trọng số? Nếu có → cân nhắc Dijkstra (Chương 30), không thì BFS/DFS đủ. 3. Đặc tính đặc biệt? DAG → topo sort, bipartite, planar, …

Biểu diễn graph 

from collections import defaultdict
from typing import List

# 1) Adjacency List - hầu hết bài dùng cái này
graph: dict[int, list[int]] = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)    # bỏ dòng này nếu directed

# 2) Edge List - input "raw"
edges: list[tuple[int, int]] = [(0, 1), (1, 2), ...]

# 3) Adjacency Matrix - chỉ khi V nhỏ (≤ 1000) và mật độ cao
adj = [[0] * n for _ in range(n)]
for u, v in edges:
    adj[u][v] = 1

Khi nào dùng cái nào?

Biểu diễn Lookup (u, v) Duyệt láng giềng u Bộ nhớ
Adj list O(deg(u)) O(deg(u)) O(V + E)
Edge list O(E) O(E) O(E)
Adj matrix O(1) O(V) O(V²)

→ Mặc định dùng adjacency list. Chỉ chuyển sang matrix khi cần kiểm tra edge O(1) và V nhỏ.

Template code 

from collections import defaultdict, deque

# DFS đệ quy
def dfs(node: int, visited: set[int], graph: dict) -> None:
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor, visited, graph)

# DFS iterative bằng stack
def dfs_iter(start: int, graph: dict) -> set[int]:
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                stack.append(nb)
    return visited

# BFS bằng queue
def bfs(start: int, graph: dict) -> set[int]:
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return visited

Bài tự luyện cuối chương

  • LC 261 - Graph Valid Tree
  • LC 332 - Reconstruct Itinerary (Eulerian path)
  • LC 444 - Sequence Reconstruction
  • LC 684 - Redundant Connection (Union Find - Chương 24)
  • LC 743 - Network Delay Time (Dijkstra - Chương 30)
  • LC 947 - Most Stones Removed (Union Find)

9.1 Find if Path Exists in Graph (LC 1971)

Đề bài

Cho n đỉnh đánh số 0..n-1 và mảng cạnh vô hướng edges[i] = [u, v]. Cho source và destination. Trả về True nếu có đường đi giữa chúng.

Ví dụ 

Input:  n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: True

Input:  n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: False

Ràng buộc

  • 1 <= n <= 2·10^5
  • 0 <= len(edges) <= 2·10^5

Clarifying questions

  • Có self-loop không? → Có thể; pattern xử lý tự nhiên.
  • Multi-edge? → Có thể.

Hướng tiếp cận

3 cách kinh điển, đều O(V + E): 1. BFS

  • duyệt theo lớp, return ngay khi gặp destination. 2. DFS - đệ quy hoặc stack. 3. Union Find (Chương 24) - gộp 2 đỉnh thành 1 root nếu có cạnh; check find(source) == find(destination). Đẹp khi đề bài có nhiều query “có đường đi giữa u, v?”.

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    """BFS - sạch nhất cho 1 query."""

    def validPath(self, n: int, edges: List[List[int]],
                  source: int, destination: int) -> bool:
        if source == destination:
            return True
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = {source}
        queue = deque([source])
        while queue:
            node = queue.popleft()
            for nb in graph[node]:
                if nb == destination:
                    return True
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        return False

Phân tích độ phức tạp

  • Thời gian: O(V + E). Bộ nhớ: O(V + E).

Bình luận

  • Khi nào chọn BFS vs DFS? Cho 1 query “có đường?”, hai cái tương đương. DFS đệ quy có rủi ro stack overflow với graph lớn (V = 10^5+).
  • Bẫy: quên source == destination → vẫn đúng vì BFS sẽ duyệt tới chính nó, nhưng check riêng cho gọn.

Bài tự luyện liên quan

  • LC 261 - Graph Valid Tree.
  • LC 547 - Number of Provinces.
  • LC 323 - Number of Connected Components (bài 9.3).

9.2 Clone Graph (LC 133)

Đề bài

Cho node của một undirected connected graph. Mỗi Node có val: int và neighbors: list[Node]. Hãy deep copy graph: tạo bản sao mà mỗi node mới là instance riêng, các neighbors trỏ vào node mới tương ứng.

Ví dụ 

Input:  adjList = [[2,4], [1,3], [2,4], [1,3]]
        (adjList[i-1] = danh sách neighbor của node i, node value 1-indexed
         giống LC; tham số API thực chất là Node = adjList[0] = node 1)

        Tương ứng graph:
            1 ── 2
            │    │
            4 ── 3

Output: [[2,4], [1,3], [2,4], [1,3]]
        (cùng cấu trúc adjacency, nhưng MỌI Node trong output là instance MỚI;
         không có Node nào dùng chung với input)

Ràng buộc

  • 0 <= số node <= 100
  • 1 <= val <= 100, val phân biệt.

Clarifying questions

  • Graph có cycle không? → Có (undirected).
  • Mỗi node có ít nhất 1 hàng xóm? → Có (connected graph).

Hướng tiếp cận

Pattern y hệt LC 138 (Copy List with Random Pointer, bài 7.8): dùng hash map original_to_copy để tránh tạo trùng và xử lý chu trình.

BFS / DFS đều OK - quan trọng là check visited qua dict.

Hình minh hoạ với graph 1-2-3-4-1:

Bắt đầu: visit 1.
  cloned = {1: Node(1)}
  queue = [1]

Pop 1:  hàng xóm = [2, 4]
  Tạo Node(2), Node(4); thêm vào cloned.
  cloned[1].neighbors = [cloned[2], cloned[4]]
  queue = [2, 4]

Pop 2:  hàng xóm = [1, 3]
  cloned[1] đã có; tạo Node(3).
  cloned[2].neighbors = [cloned[1], cloned[3]]
  queue = [4, 3]

Pop 4:  hàng xóm = [1, 3]
  cả 2 đã có trong cloned.
  cloned[4].neighbors = [cloned[1], cloned[3]]

Pop 3:  hàng xóm = [2, 4]
  cả 2 đã có.
  cloned[3].neighbors = [cloned[2], cloned[4]]

→ Trả cloned[1] làm head của bản copy.

Code Python 3 

from collections import deque

class Node:
    def __init__(self, val: int = 0, neighbors: "list[Node] | None" = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution:
    """BFS với hash map."""

    def cloneGraph(self, node: "Node | None") -> "Node | None":
        if not node:
            return None

        cloned: dict["Node", "Node"] = {node: Node(node.val)}
        queue: deque["Node"] = deque([node])

        while queue:
            cur = queue.popleft()
            for nb in cur.neighbors:
                if nb not in cloned:
                    cloned[nb] = Node(nb.val)
                    queue.append(nb)
                cloned[cur].neighbors.append(cloned[nb])

        return cloned[node]


class SolutionDFS:
    """DFS đệ quy - code ngắn hơn."""

    def cloneGraph(self, node: "Node | None") -> "Node | None":
        cloned: dict["Node", "Node"] = {}

        def dfs(cur: "Node") -> "Node":
            if cur in cloned:
                return cloned[cur]
            copy = Node(cur.val)
            cloned[cur] = copy           # phải set TRƯỚC khi đệ quy neighbors
            copy.neighbors = [dfs(nb) for nb in cur.neighbors]
            return copy

        return dfs(node) if node else None

Phân tích độ phức tạp

  • Thời gian: O(V + E).
  • Bộ nhớ: O(V) cho cloned.

Bình luận

  • Bẫy lớn nhất: trong DFS, phải set cloned[cur] = copy trước khi đệ quy hàng xóm - nếu không, chu trình sẽ gây infinite recursion.
  • Khi nào BFS vs DFS? Như mọi bài “clone with reference”, cả 2 tương đương O(V + E). BFS dễ tránh stack overflow.

Bài tự luyện liên quan

  • LC 138 - Copy List with Random Pointer (bài 7.8).
  • LC 1485 - Clone Binary Tree With Random Pointer.
  • LC 1490 - Clone N-ary Tree.

9.3 Number of Connected Components (LC 323)

Đề bài

Cho n đỉnh đánh số 0..n-1 và mảng cạnh vô hướng. Đếm số thành phần liên thông.

Ví dụ 

Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Giải thích: 2 component {0,1,2} và {3,4}.

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

Ràng buộc

  • 1 <= n <= 2000
  • 0 <= len(edges) <= n*(n-1)/2

Clarifying questions

  • Self-loop tính component không? → Mỗi node là 1 component nếu không có edge.
  • Multi-edge? → Có thể.

Hướng tiếp cận

Cách 1 - Duyệt DFS/BFS từng đỉnh chưa thăm - O(V + E). Cho mỗi đỉnh chưa thăm, tăng counter và DFS/BFS đánh dấu cả component.

Cách 2 - Union Find - O((V + E) · α(V)). Gom các đỉnh có cạnh thành cùng root. Đếm số root khác nhau.

Code Python 3 

from collections import defaultdict
from typing import List

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * n
        count = 0

        def dfs(node: int) -> None:
            visited[node] = True
            for nb in graph[node]:
                if not visited[nb]:
                    dfs(nb)

        for i in range(n):
            if not visited[i]:
                count += 1
                dfs(i)
        return count


class SolutionUF:
    """Union Find - đẹp khi đề bài có nhiều query."""

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path compression
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            parent[px] = py
            return True

        components = n
        for u, v in edges:
            if union(u, v):
                components -= 1
        return components

Phân tích độ phức tạp

  • DFS: O(V + E) time, O(V + E) space.
  • Union Find: O((V + E) · α(V)) time, O(V) space.

Bình luận

  • Khi đề bài có thao tác “thêm cạnh dần dần” → Union Find tự nhiên hơn (xem Chương 24).
  • DFS đệ quy có thể stack overflow với V rất lớn → fallback iterative.

Bài tự luyện liên quan

  • LC 547 - Number of Provinces.
  • LC 200 - Number of Islands (Chương 12).
  • LC 305 - Number of Islands II (Union Find).

9.4 Course Schedule (LC 207)

Đề bài

Có numCourses khoá học đánh số 0..numCourses-1. prerequisites[i] = [a, b] nghĩa là muốn học khoá a thì phải hoàn thành khoá b trước. Trả về True nếu có thể học hết tất cả khoá, ngược lại False.

Ví dụ 

Input:  numCourses = 2, prerequisites = [[1, 0]]
Output: True

Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False    (vòng tròn: 1 cần 0, 0 cần 1)

Ràng buộc

  • 1 <= numCourses <= 2000
  • 0 <= len(prerequisites) <= 5000

Clarifying questions

  • Đề có self-loop / cycle không? → Có thể; cần detect cycle.

Hướng tiếp cận

Phát biểu lại: Tạo directed graph b → a (b phải xong trước a). Câu hỏi: graph có chu trình không? Nếu không có chu trình → có thể học hết.

Cách 1 - DFS với 3 trạng thái (white / gray / black).

  • white = chưa thăm.
  • gray = đang trong recursion path hiện tại.
  • black = đã thăm xong, không có chu trình từ đây.

Nếu DFS gặp gray → tìm thấy back-edge → có chu trình.

Cách 2 - Topological Sort BFS (Kahn’s algorithm).

Đếm indegree mỗi node. Đẩy các node indegree == 0 vào queue. Pop và giảm indegree của các neighbors. Nếu cuối cùng đếm được numCourses node → DAG; ngược lại có chu trình.

Topological sort là cốt lõi của Chương 13. Ở đây giới thiệu sớm vì Course Schedule là kinh điển ứng dụng nó.

Hình minh hoạ - DFS 3 màu với cycle 0 → 1 → 0:

Bắt đầu: tất cả white.
DFS(0):
  mark 0 = gray.
  visit 1 (white):
    DFS(1):
      mark 1 = gray.
      visit 0 (gray!) → back-edge phát hiện → return False (có chu trình)

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    """DFS 3-color."""

    WHITE, GRAY, BLACK = 0, 1, 2

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)            # b → a

        color = [self.WHITE] * numCourses

        def has_cycle(node: int) -> bool:
            if color[node] == self.GRAY:
                return True               # back-edge
            if color[node] == self.BLACK:
                return False              # đã xong, không có cycle từ đây
            color[node] = self.GRAY
            for nb in graph[node]:
                if has_cycle(nb):
                    return True
            color[node] = self.BLACK
            return False

        for i in range(numCourses):
            if has_cycle(i):
                return False
        return True


class SolutionKahn:
    """BFS topo sort (Kahn's algorithm)."""

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1

        queue = deque(i for i, d in enumerate(indeg) if d == 0)
        processed = 0
        while queue:
            node = queue.popleft()
            processed += 1
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return processed == numCourses

Phân tích độ phức tạp

  • Thời gian: O(V + E).
  • Bộ nhớ: O(V + E).

Bình luận

  • Khi nào DFS vs Kahn?
    • DFS dễ extend cho bài liệt kê chu trình thực.
    • Kahn dễ extend cho LC 210 - Course Schedule II (trả về thứ tự học, Chương 13).
  • Bẫy: chiều cạnh. Đề bảo “muốn học a phải xong b” → cạnh b → a (b enable a). Vẽ đúng chiều là 50% thành công.

Bài tự luyện liên quan

  • LC 210 - Course Schedule II.
  • LC 802 - Find Eventual Safe States.
  • LC 269 - Alien Dictionary (Chương 13).

9.5 Is Graph Bipartite? (LC 785)

Đề bài

Cho graph vô hướng dạng adjacency list graph[i] = [hàng xóm của i]. Trả về True nếu graph là bipartite - có thể chia các đỉnh thành 2 tập sao cho mọi cạnh nối 2 đỉnh ở khác tập.

Ví dụ 

Input:  graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: False
Giải thích: 0-1-2-0 là tam giác → không thể 2-color.

Input:  graph = [[1,3],[0,2],[1,3],[0,2]]
Output: True
Giải thích: tập A = {0, 2}, tập B = {1, 3}.

Ràng buộc

  • 1 <= n <= 100
  • 0 <= graph[i].length < n

Clarifying questions

  • Graph có thể không liên thông? → Có - phải loop qua mọi component.
  • Self-loop? → Coi như xung đột → không bipartite.

Hướng tiếp cận

Equivalent: Graph bipartite ↔︎ tô được 2 màu sao cho không có 2 đỉnh kề nhau cùng màu.

BFS/DFS với 2-color: Bắt đầu mỗi component, tô đỉnh đầu màu 0. Khi BFS/DFS sang hàng xóm, tô màu ngược. Nếu gặp hàng xóm đã có màu giống → return False.

Hình minh hoạ - graph tam giác (không bipartite):

       0
      / \
     1───2

BFS từ 0:
  color[0] = 0.
  Sang 1: color[1] = 1 (ngược màu 0).
  Sang 2: color[2] = 1 (ngược màu 0).
  Từ 1, sang 2: color[2] đã là 1 == color[1] = 1 → MÂU THUẪN → False

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n        # -1 = chưa tô

        for start in range(n):
            if color[start] != -1:
                continue
            # BFS component chứa start.
            color[start] = 0
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for nb in graph[node]:
                    if color[nb] == -1:
                        color[nb] = 1 - color[node]
                        queue.append(nb)
                    elif color[nb] == color[node]:
                        return False
        return True

Phân tích độ phức tạp

  • Thời gian: O(V + E).
  • Bộ nhớ: O(V).

Bình luận

  • Tại sao loop for start in range(n)? Graph có thể không liên thông - phải khởi động BFS ở mọi component.
  • Định lý: Graph bipartite ↔︎ không có chu trình lẻ (odd cycle). 2-coloring chính là chứng minh xây dựng.
  • Follow-up:
    • LC 886 - Possible Bipartition: cùng pattern, input là “không thích nhau”.
    • Bipartite matching (Hungarian algorithm) - vượt khỏi phạm vi sách.

Bài tự luyện liên quan

  • LC 886 - Possible Bipartition.
  • LC 1042 - Flower Planting With No Adjacent.
  • LC 1697 - Checking Existence of Edge Length Limited Paths.

9.6 Evaluate Division (LC 399)

Đề bài

Cho mảng các đẳng thức equations[i] = [Ai, Bi] và mảng values[i] nghĩa là Ai / Bi = values[i]. Cho mảng query queries[j] = [Cj, Dj]. Hãy trả lời mỗi query với giá trị Cj / Dj, hoặc -1 nếu không xác định được.

Ví dụ 

Input:  equations = [["a","b"], ["b","c"]]
        values    = [2.0, 3.0]
        queries   = [["a","c"], ["b","a"], ["a","e"], ["a","a"], ["x","x"]]
Output: [6.0, 0.5, -1.0, 1.0, -1.0]
Giải thích:
  a/c = a/b * b/c = 2 * 3 = 6
  b/a = 1/(a/b) = 0.5
  a/e không xác định (e không có trong equations)
  a/a = 1
  x/x: x không có trong equations → -1

Ràng buộc

  • 1 <= len(equations) <= 20
  • 0.0 < values[i] <= 20.0

Clarifying questions

  • Phép chia 0 / variable không tồn tại? → Trả -1.
  • Có thể có chu trình (mâu thuẫn) không? → Theo đề: không.

Hướng tiếp cận

Insight: mỗi đẳng thức A / B = k ↔︎ trong directed graph có 2 cạnh: - A → B trọng số k. - B → A trọng số 1/k.

Khi đó C / D = tích trọng số dọc theo bất kỳ đường đi nào từ C đến D. Nếu không có đường đi → trả -1.

DFS trên graph trọng số là đủ. Tối ưu hơn: Union Find với trọng số (xem Chương 24).

Hình minh hoạ với equations a/b=2, b/c=3:

Graph trọng số:
            ── 2 ──>          ── 3 ──>
       a               b               c
            <─ 0.5 ──         <─ 1/3 ─

Query a/c: DFS từ a:
  a → b (× 2), tiếp b → c (× 3) → tổng 2 * 3 = 6.  ✓

Code Python 3 

from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(
        self, equations: List[List[str]],
        values: List[float], queries: List[List[str]]
    ) -> List[float]:
        graph: dict[str, dict[str, float]] = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = v
            graph[b][a] = 1.0 / v

        def dfs(src: str, dst: str, visited: set[str]) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for nb, weight in graph[src].items():
                if nb in visited:
                    continue
                sub = dfs(nb, dst, visited)
                if sub != -1.0:
                    return weight * sub
            return -1.0

        return [dfs(c, d, set()) for c, d in queries]

Phân tích độ phức tạp

  • Thời gian: O(Q · (V + E)) với Q = số queries.
  • Bộ nhớ: O(V + E).

Bình luận

  • Bẫy thường gặp:
    • Quên src == dst base case → return -1 cả với a/a.
    • Quên check src not in graph → query với variable không tồn tại.
    • Tạo visited mới cho mỗi query - chia sẻ visited giữa query sẽ ban đường đi.
  • Follow-up - Union Find weighted (Chương 24):
    • Mỗi find(x) không chỉ trả root mà còn tích trọng số trên đường lên root.
    • Sau preprocessing, mỗi query là O(α(V)).
  • Liên hệ thực tế: đổi đơn vị (mét/inch/feet), tỷ giá tiền tệ, …

Bài tự luyện liên quan

  • LC 1631 - Path With Minimum Effort (Chương 37).
  • LC 1976 - Number of Ways to Arrive at Destination.
  • LC 990 - Satisfiability of Equality Equations (Union Find).

Tóm tắt chương & Quyết định

Graph problem diagnosis

Triệu chứng đề bài Pattern phù hợp Chương
“Có đường từ A đến B?” BFS / DFS / Union Find 10, 11, 24
“Số cụm/đảo” DFS / Union Find 12, 24
“Thứ tự thực hiện với ràng buộc” Topological sort 13
“Shortest path trọng số dương” Dijkstra (Chương 30)  
“Shortest path 0/1 edges” 0-1 BFS / BFS thường  
“All-pairs shortest” Floyd-Warshall O(V³)  
“Nhỏ nhất kết nối tất cả” MST (Chương 33)  
“Bottleneck min/max trên path” Kruskal + DSU / BS + BFS (37)  
“Bipartite?” BFS/DFS 2-color  

Clone Graph (LC 133) - mapping diagram 

old:  1 - 2
       \  /
        3 - 4

old_to_new = {1:1', 2:2', 3:3', 4:4'}   (dict cũ → bản sao)
clone(node):
    if node in old_to_new: return old_to_new[node]
    new = Node(node.val)
    old_to_new[node] = new       # ĐẶT TRƯỚC khi đệ quy → tránh vòng
    for nei in node.neighbors:
        new.neighbors.append(clone(nei))
    return new

Evaluate Division (LC 399) - weighted DFS

  • Coi a / b = w là cạnh có trọng số: từ a đi sang b “nhân với w”.
  • Hỏi x / y: tìm đường đi x → y, kết quả là tích các trọng số dọc đường.
  • Không có đường → -1.0.

Course Schedule ở chương này = teaser

Bài đầy đủ Topological sort xem Chương 13. Chương này chỉ trình bày DFS detect cycle.