Graphs & Graph Algorithms: Hướng Dẫn Toàn Diện

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

A → [B, C]
B → [C]
C → [D]
D → []

// TypeScript - Graph dùng Adjacency List
class Graph {
  private adjacencyList: Map<number, number[]>;
  private directed: boolean;
 
  constructor(directed = false) {
    this.adjacencyList = new Map();
    this.directed = directed;
  }
 
  addVertex(vertex: number): void {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }
 
  addEdge(u: number, v: number): void {
    this.addVertex(u);
    this.addVertex(v);
    this.adjacencyList.get(u)!.push(v);
    if (!this.directed) {
      this.adjacencyList.get(v)!.push(u); // undirected: thêm cả hai chiều
    }
  }
 
  getNeighbors(vertex: number): number[] {
    return this.adjacencyList.get(vertex) ?? [];
  }
 
  getVertices(): number[] {
    return Array.from(this.adjacencyList.keys());
  }
 
  print(): void {
    for (const [vertex, neighbors] of this.adjacencyList) {
      console.log(`${vertex} → [${neighbors.join(', ')}]`);
    }
  }
}
 
// Undirected Graph
const g = new Graph();
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.print();
// 0 → [1, 2]
// 1 → [0, 3]
// 2 → [0, 3]
// 3 → [1, 2, 4]
// 4 → [3]
 
// Directed Graph
const dg = new Graph(true);
dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(1, 3);
dg.print();
// 0 → [1, 2]
// 1 → [3]
// 2 → []
// 3 → []

# Python - Graph dùng Adjacency List
from collections import defaultdict
 
class Graph:
    def __init__(self, directed=False):
        self.adjacency_list = defaultdict(list)
        self.directed = directed
 
    def add_vertex(self, vertex: int) -> None:
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []
 
    def add_edge(self, u: int, v: int) -> None:
        self.adjacency_list[u].append(v)
        if not self.directed:
            self.adjacency_list[v].append(u)
 
    def get_neighbors(self, vertex: int) -> list[int]:
        return self.adjacency_list[vertex]
 
    def print_graph(self) -> None:
        for vertex, neighbors in self.adjacency_list.items():
            print(f"{vertex} → {neighbors}")
 
# Dùng thử
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()

// TypeScript - Weighted Graph
class WeightedGraph {
  private adjacencyList: Map<number, [number, number][]>; // [neighbor, weight]
 
  constructor() {
    this.adjacencyList = new Map();
  }
 
  addEdge(u: number, v: number, weight: number): void {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push([v, weight]);
    this.adjacencyList.get(v)!.push([u, weight]); // undirected
  }
 
  getNeighbors(vertex: number): [number, number][] {
    return this.adjacencyList.get(vertex) ?? [];
  }
}

# Python - Weighted Graph
class WeightedGraph:
    def __init__(self):
        self.adjacency_list = defaultdict(list)  # {node: [(neighbor, weight), ...]}
 
    def add_edge(self, u: int, v: int, weight: int) -> None:
        self.adjacency_list[u].append((v, weight))
        self.adjacency_list[v].append((u, weight))  # undirected

// TypeScript - BFS
function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const queue: number[] = [start];
  const result: number[] = [];
 
  visited.add(start);
 
  while (queue.length > 0) {
    const vertex = queue.shift()!; // dequeue từ đầu
    result.push(vertex);
 
    for (const neighbor of graph.get(vertex) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
 
  return result;
}
 
// Build graph dạng adjacency list Map
const graph = new Map<number, number[]>([
  [0, [1, 2]],
  [1, [0, 3, 4]],
  [2, [0, 5]],
  [3, [1]],
  [4, [1]],
  [5, [2]],
]);
 
console.log(bfs(graph, 0)); // [0, 1, 2, 3, 4, 5]

# Python - BFS
from collections import deque
 
def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = set([start])
    queue = deque([start])
    result = []
 
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
 
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return result

// TypeScript - BFS Shortest Path
function bfsShortestPath(
  graph: Map<number, number[]>,
  start: number,
  end: number
): number[] | null {
  if (start === end) return [start];
 
  const visited = new Set<number>([start]);
  // Queue lưu [vertex, path để đến nó]
  const queue: [number, number[]][] = [[start, [start]]];
 
  while (queue.length > 0) {
    const [vertex, path] = queue.shift()!;
 
    for (const neighbor of graph.get(vertex) ?? []) {
      if (neighbor === end) return [...path, neighbor];
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
 
  return null; // không tìm thấy path
}

# Python - BFS Shortest Path
def bfs_shortest_path(graph: dict, start: int, end: int) -> list[int] | None:
    if start == end:
        return [start]
 
    visited = {start}
    queue = deque([(start, [start])])
 
    while queue:
        vertex, path = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
 
    return None  # không tìm thấy path

// TypeScript - DFS Đệ Quy
function dfsRecursive(
  graph: Map<number, number[]>,
  vertex: number,
  visited: Set<number> = new Set(),
  result: number[] = []
): number[] {
  visited.add(vertex);
  result.push(vertex);
 
  for (const neighbor of graph.get(vertex) ?? []) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited, result);
    }
  }
 
  return result;
}

# Python - DFS Đệ Quy
def dfs_recursive(graph: dict, vertex: int, visited: set = None, result: list = None) -> list[int]:
    if visited is None:
        visited = set()
    if result is None:
        result = []
 
    visited.add(vertex)
    result.append(vertex)
 
    for neighbor in graph.get(vertex, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
 
    return result

// TypeScript - DFS Iterative
function dfsIterative(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const stack: number[] = [start];
  const result: number[] = [];
 
  while (stack.length > 0) {
    const vertex = stack.pop()!; // pop từ đỉnh (LIFO)
    if (visited.has(vertex)) continue;
 
    visited.add(vertex);
    result.push(vertex);
 
    // Push neighbors theo thứ tự ngược để duyệt từ trái sang phải
    for (const neighbor of [...(graph.get(vertex) ?? [])].reverse()) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
 
  return result;
}

# Python - DFS Iterative
def dfs_iterative(graph: dict, start: int) -> list[int]:
    visited = set()
    stack = [start]
    result = []
 
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        result.append(vertex)
        for neighbor in reversed(graph.get(vertex, [])):
            if neighbor not in visited:
                stack.append(neighbor)
 
    return result

// TypeScript - Đếm Connected Components
function countComponents(n: number, edges: number[][]): number {
  // Build adjacency list
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u);
  }
 
  const visited = new Set<number>();
  let components = 0;
 
  function dfs(vertex: number): void {
    visited.add(vertex);
    for (const neighbor of graph.get(vertex) ?? []) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
  }
 
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      dfs(i);
      components++;
    }
  }
 
  return components;
}
 
// Ví dụ: 5 vertices, edges [[0,1],[1,2],[3,4]]
// → 2 components: {0,1,2} và {3,4}
console.log(countComponents(5, [[0,1],[1,2],[3,4]])); // 2

# Python - Đếm Connected Components
def count_components(n: int, edges: list[list[int]]) -> int:
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
 
    def dfs(vertex: int) -> None:
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
 
    components = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            components += 1
 
    return components

// TypeScript - Phát Hiện Cycle trong Undirected Graph
function hasCycleUndirected(n: number, edges: number[][]): boolean {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u);
  }
 
  const visited = new Set<number>();
 
  function dfs(vertex: number, parent: number): boolean {
    visited.add(vertex);
    for (const neighbor of graph.get(vertex) ?? []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, vertex)) return true;
      } else if (neighbor !== parent) {
        return true; // đã visited và không phải parent → có cycle!
      }
    }
    return false;
  }
 
  for (let i = 0; i < n; i++) {
    if (!visited.has(i) && dfs(i, -1)) return true;
  }
 
  return false;
}

# Python - Phát Hiện Cycle trong Undirected Graph
def has_cycle_undirected(n: int, edges: list[list[int]]) -> bool:
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
 
    def dfs(vertex: int, parent: int) -> bool:
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                return True  # back edge → có cycle
        return False
 
    for i in range(n):
        if i not in visited and dfs(i, -1):
            return True
 
    return False

// TypeScript - Phát Hiện Cycle trong Directed Graph
function hasCycleDirected(n: number, edges: number[][]): boolean {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) graph.get(u)!.push(v);
 
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(n).fill(WHITE);
 
  function dfs(vertex: number): boolean {
    color[vertex] = GRAY; // đánh dấu đang xử lý
 
    for (const neighbor of graph.get(vertex) ?? []) {
      if (color[neighbor] === GRAY) return true; // back edge → có cycle!
      if (color[neighbor] === WHITE && dfs(neighbor)) return true;
    }
 
    color[vertex] = BLACK; // đã xử lý xong
    return false;
  }
 
  for (let i = 0; i < n; i++) {
    if (color[i] === WHITE && dfs(i)) return true;
  }
 
  return false;
}

# Python - Phát Hiện Cycle trong Directed Graph
def has_cycle_directed(n: int, edges: list[list[int]]) -> bool:
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
 
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
 
    def dfs(vertex: int) -> bool:
        color[vertex] = GRAY
        for neighbor in graph[vertex]:
            if color[neighbor] == GRAY:
                return True  # có cycle!
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[vertex] = BLACK
        return False
 
    for i in range(n):
        if color[i] == WHITE and dfs(i):
            return True
 
    return False

// TypeScript - Topological Sort (DFS)
function topologicalSortDFS(n: number, edges: number[][]): number[] {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) graph.get(u)!.push(v);
 
  const visited = new Set<number>();
  const result: number[] = [];
 
  function dfs(vertex: number): void {
    visited.add(vertex);
    for (const neighbor of graph.get(vertex) ?? []) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    result.push(vertex); // thêm SAU KHI tất cả descendants xong
  }
 
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) dfs(i);
  }
 
  return result.reverse(); // đảo ngược để có thứ tự topological
}
 
// Ví dụ: 4 môn học, prerequisites [[0,2],[1,2],[1,3],[2,3]]
// → thứ tự hợp lệ: [0, 1, 2, 3] hoặc [1, 0, 2, 3]

# Python - Topological Sort (DFS)
def topological_sort_dfs(n: int, edges: list[list[int]]) -> list[int]:
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
 
    visited = set()
    result = []
 
    def dfs(vertex: int) -> None:
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(vertex)  # append sau khi tất cả descendants xong
 
    for i in range(n):
        if i not in visited:
            dfs(i)
 
    return result[::-1]  # đảo ngược

// TypeScript - Giải Thuật Kahn
function topologicalSortKahn(n: number, edges: number[][]): number[] | null {
  const graph = new Map<number, number[]>();
  const inDegree = new Array(n).fill(0);
 
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    inDegree[v]++;
  }
 
  // Bắt đầu với tất cả vertices không có prerequisite
  const queue: number[] = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
 
  const result: number[] = [];
 
  while (queue.length > 0) {
    const vertex = queue.shift()!;
    result.push(vertex);
 
    for (const neighbor of graph.get(vertex) ?? []) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
 
  // Nếu result không bao gồm tất cả vertices → có cycle
  return result.length === n ? result : null;
}

# Python - Giải Thuật Kahn
from collections import deque
 
def topological_sort_kahn(n: int, edges: list[list[int]]) -> list[int] | None:
    graph = {i: [] for i in range(n)}
    in_degree = [0] * n
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
 
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    return result if len(result) == n else None  # None nghĩa là phát hiện cycle

// TypeScript - Giải Thuật Dijkstra (giả lập min-heap bằng sorted array)
function dijkstra(
  graph: Map<number, [number, number][]>, // node → [(neighbor, weight)]
  start: number
): Map<number, number> {
  const distances = new Map<number, number>();
  const visited = new Set<number>();
 
  // Khởi tạo tất cả distances là Infinity
  for (const vertex of graph.keys()) {
    distances.set(vertex, Infinity);
  }
  distances.set(start, 0);
 
  // Giả lập priority queue: [distance, vertex]
  const pq: [number, number][] = [[0, start]];
 
  while (pq.length > 0) {
    // Lấy vertex có distance nhỏ nhất
    pq.sort((a, b) => a[0] - b[0]);
    const [dist, vertex] = pq.shift()!;
 
    if (visited.has(vertex)) continue;
    visited.add(vertex);
 
    for (const [neighbor, weight] of graph.get(vertex) ?? []) {
      const newDist = dist + weight;
      if (newDist < (distances.get(neighbor) ?? Infinity)) {
        distances.set(neighbor, newDist);
        pq.push([newDist, neighbor]);
      }
    }
  }
 
  return distances;
}
 
// Dùng thử
const wGraph = new Map<number, [number, number][]>([
  [0, [[1, 4], [2, 2]]],
  [1, [[3, 3]]],
  [2, [[1, 1], [3, 5]]],
  [3, [[4, 1]]],
  [4, []],
]);
 
const dist = dijkstra(wGraph, 0);
console.log(dist); // Map { 0 → 0, 1 → 3, 2 → 2, 3 → 6, 4 → 7 }

# Python - Giải Thuật Dijkstra (dùng heapq)
import heapq
 
def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
    # graph[u] = [(v, weight), ...]
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
 
    # Min-heap: (distance, vertex)
    heap = [(0, start)]
 
    while heap:
        dist, vertex = heapq.heappop(heap)
 
        if dist > distances[vertex]:
            continue  # entry cũ, bỏ qua
 
        for neighbor, weight in graph.get(vertex, []):
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
 
    return distances
 
# Dùng thử
graph = {
    0: [(1, 4), (2, 2)],
    1: [(3, 3)],
    2: [(1, 1), (3, 5)],
    3: [(4, 1)],
    4: [],
}
print(dijkstra(graph, 0))  # {0: 0, 1: 3, 2: 2, 3: 6, 4: 7}

// TypeScript - Union-Find với Path Compression + Union by Rank
class UnionFind {
  private parent: number[];
  private rank: number[];
 
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i); // mỗi node là parent của chính nó
    this.rank = new Array(n).fill(0);
  }
 
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
 
  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);
 
    if (rootX === rootY) return false; // đã trong cùng component
 
    // Union by rank: gắn cây nhỏ hơn dưới cây lớn hơn
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
 
    return true; // merge hai components khác nhau
  }
 
  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}
 
// Dùng thử
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
console.log(uf.connected(0, 2)); // true  (cùng component)
console.log(uf.connected(0, 3)); // false (khác component)

# Python - Union-Find
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
 
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
 
    def union(self, x: int, y: int) -> bool:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # đã connected
 
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
 
        return True  # đã merge
 
    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

// TypeScript - Number of Islands
function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
 
  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // đánh dấu visited bằng cách "chìm" đảo
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
 
  return count;
}
 
// grid = [["1","1","0"],["0","1","0"],["0","0","1"]] → 2

# Python - Number of Islands
def num_islands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    count = 0
 
    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'  # đánh dấu visited
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
 
    return count

// TypeScript - Clone Graph
class GraphNode {
  val: number;
  neighbors: GraphNode[];
  constructor(val = 0, neighbors: GraphNode[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}
 
function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (!node) return null;
 
  const visited = new Map<GraphNode, GraphNode>();
 
  function dfs(curr: GraphNode): GraphNode {
    if (visited.has(curr)) return visited.get(curr)!;
 
    const clone = new GraphNode(curr.val);
    visited.set(curr, clone);
 
    for (const neighbor of curr.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
 
    return clone;
  }
 
  return dfs(node);
}

# Python - Clone Graph
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []
 
def clone_graph(node: 'Node | None') -> 'Node | None':
    if not node:
        return None
 
    visited = {}  # old_node → clone
 
    def dfs(curr: Node) -> Node:
        if curr in visited:
            return visited[curr]
        clone = Node(curr.val)
        visited[curr] = clone
        for neighbor in curr.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone
 
    return dfs(node)

// TypeScript - Course Schedule
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < numCourses; i++) graph.set(i, []);
  for (const [course, prereq] of prerequisites) {
    graph.get(prereq)!.push(course);
  }
 
  // 0 = chưa visited, 1 = đang xử lý, 2 = xong
  const state = new Array(numCourses).fill(0);
 
  function hasCycle(node: number): boolean {
    if (state[node] === 1) return true;  // cycle!
    if (state[node] === 2) return false; // đã an toàn
 
    state[node] = 1; // đánh dấu đang xử lý
    for (const next of graph.get(node) ?? []) {
      if (hasCycle(next)) return true;
    }
    state[node] = 2; // đánh dấu xong
    return false;
  }
 
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
 
  return true;
}

# Python - Course Schedule
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)
 
    UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
    state = [UNVISITED] * num_courses
 
    def has_cycle(node: int) -> bool:
        if state[node] == IN_PROGRESS:
            return True
        if state[node] == DONE:
            return False
        state[node] = IN_PROGRESS
        for nxt in graph[node]:
            if has_cycle(nxt):
                return True
        state[node] = DONE
        return False
 
    return not any(has_cycle(i) for i in range(num_courses))

// TypeScript - Word Ladder
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
 
  const queue: [string, number][] = [[beginWord, 1]]; // [word, số bước]
  const visited = new Set([beginWord]);
 
  while (queue.length > 0) {
    const [word, steps] = queue.shift()!;
 
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) { // 'a' đến 'z'
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        if (newWord === endWord) return steps + 1;
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, steps + 1]);
        }
      }
    }
  }
 
  return 0; // không tìm thấy chuỗi chuyển đổi
}

# Python - Word Ladder
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    word_set = set(word_list)
    if end_word not in word_set:
        return 0
 
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
 
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                if new_word == end_word:
                    return steps + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))
 
    return 0

// TypeScript - Pacific Atlantic Water Flow
function pacificAtlantic(heights: number[][]): number[][] {
  const rows = heights.length;
  const cols = heights[0].length;
  const pacific = new Set<string>();
  const atlantic = new Set<string>();
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
 
  function bfs(starts: number[][], visited: Set<string>): void {
    const queue: number[][] = [...starts];
    for (const [r, c] of starts) visited.add(`${r},${c}`);
 
    while (queue.length > 0) {
      const [r, c] = queue.shift()!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        const key = `${nr},${nc}`;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (visited.has(key)) continue;
        if (heights[nr][nc] < heights[r][c]) continue; // nước chảy xuống; chúng ta đi lên
        visited.add(key);
        queue.push([nr, nc]);
      }
    }
  }
 
  // Thái Bình Dương: hàng trên + cột trái
  const pacificStarts = [
    ...Array.from({ length: rows }, (_, r) => [r, 0]),
    ...Array.from({ length: cols }, (_, c) => [0, c]),
  ];
  // Đại Tây Dương: hàng dưới + cột phải
  const atlanticStarts = [
    ...Array.from({ length: rows }, (_, r) => [r, cols - 1]),
    ...Array.from({ length: cols }, (_, c) => [rows - 1, c]),
  ];
 
  bfs(pacificStarts, pacific);
  bfs(atlanticStarts, atlantic);
 
  const result: number[][] = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (pacific.has(`${r},${c}`) && atlantic.has(`${r},${c}`)) {
        result.push([r, c]);
      }
    }
  }
 
  return result;
}

# Python - Pacific Atlantic Water Flow
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
    rows, cols = len(heights), len(heights[0])
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
 
    def bfs(starts: list[tuple[int,int]]) -> set[tuple[int,int]]:
        visited = set(starts)
        queue = deque(starts)
        while queue:
            r, c = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and (nr, nc) not in visited
                        and heights[nr][nc] >= heights[r][c]):
                    visited.add((nr, nc))
                    queue.append((nr, nc))
        return visited
 
    pacific_starts = [(r, 0) for r in range(rows)] + [(0, c) for c in range(cols)]
    atlantic_starts = [(r, cols-1) for r in range(rows)] + [(rows-1, c) for c in range(cols)]
 
    pacific = bfs(pacific_starts)
    atlantic = bfs(atlantic_starts)
 
    return [[r, c] for r in range(rows) for c in range(cols) if (r, c) in pacific and (r, c) in atlantic]

// TypeScript - Redundant Connection
function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const uf = new UnionFind(n + 1); // 1-indexed
 
  for (const [u, v] of edges) {
    if (!uf.union(u, v)) return [u, v]; // đã connected → thừa
  }
 
  return [];
}
 
// edges = [[1,2],[1,3],[2,3]] → [2,3] (edge tạo ra cycle)

# Python - Redundant Connection
def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    uf = UnionFind(n + 1)  # 1-indexed
 
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # đã trong cùng component
 
    return []

// TypeScript - Cheapest Flights Within K Stops
function findCheapestPrice(
  n: number, flights: number[][], src: number, dst: number, k: number
): number {
  const graph = new Map<number, [number, number][]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [from, to, price] of flights) {
    graph.get(from)!.push([to, price]);
  }
 
  // [cost, node, stops_remaining]
  const pq: [number, number, number][] = [[0, src, k + 1]];
  const visited = new Map<number, number>(); // node → max stops đã thấy
 
  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [cost, node, stopsLeft] = pq.shift()!;
 
    if (node === dst) return cost;
    if (stopsLeft === 0) continue;
 
    // Bỏ qua nếu đã visited node này với nhiều stops hơn
    if ((visited.get(node) ?? -1) >= stopsLeft) continue;
    visited.set(node, stopsLeft);
 
    for (const [next, price] of graph.get(node) ?? []) {
      pq.push([cost + price, next, stopsLeft - 1]);
    }
  }
 
  return -1;
}

# Python - Cheapest Flights Within K Stops
def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    graph = defaultdict(list)
    for frm, to, price in flights:
        graph[frm].append((to, price))
 
    # (cost, node, stops_remaining)
    heap = [(0, src, k + 1)]
    visited = {}  # node → max stops_remaining đã thấy
 
    while heap:
        cost, node, stops_left = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops_left == 0:
            continue
        if visited.get(node, -1) >= stops_left:
            continue
        visited[node] = stops_left
        for nxt, price in graph[node]:
            heapq.heappush(heap, (cost + price, nxt, stops_left - 1))
 
    return -1

// TypeScript - Graph Valid Tree
function validTree(n: number, edges: number[][]): boolean {
  // Phải có đúng n-1 edges
  if (edges.length !== n - 1) return false;
 
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u);
  }
 
  // BFS từ node 0 — phải visit tất cả n nodes
  const visited = new Set<number>([0]);
  const queue = [0];
 
  while (queue.length > 0) {
    const node = queue.shift()!;
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
 
  return visited.size === n; // tất cả nodes có thể đến → valid tree
}

# Python - Graph Valid Tree
def valid_tree(n: int, edges: list[list[int]]) -> bool:
    if len(edges) != n - 1:
        return False
 
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = {0}
    queue = deque([0])
 
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return len(visited) == n