export function maxFlow(
  numNodes: number,
  edges: number[][],
  source: number,
  sink: number
): number {
  const capacity: number[][] = Array.from({ length: numNodes }, () => Array(numNodes).fill(0));
  const adj: number[][] = Array.from({ length: numNodes }, () => []);

  for (const [u, v, cap] of edges) {
    if (capacity[u][v] === 0 && capacity[v][u] === 0) {
      adj[u].push(v);
      adj[v].push(u);
    }

    capacity[u][v] += cap;
  }

  let totalFlow = 0;
  const parent = new Array(numNodes).fill(-1);

  const bfs = (): boolean => {
    parent.fill(-1);
    parent[source] = source;

    const queue: number[] = [source];
    let head = 0;

    while (head < queue.length) {
      const curr = queue[head++];

      for (const next of adj[curr]) {

        if (parent[next] === -1 && capacity[curr][next] > 0) {
          parent[next] = curr;

          if (next === sink) return true;

          queue.push(next);
        }
      }
    }
    return false;
  };

  while (bfs()) {
    let pathFlow = Infinity;

    for (let v = sink; v !== source; v = parent[v]) {
      const u = parent[v];
      pathFlow = Math.min(pathFlow, capacity[u][v]);
    }

    for (let v = sink; v !== source; v = parent[v]) {
      const u = parent[v];
      capacity[u][v] -= pathFlow;
      capacity[v][u] += pathFlow;
    }

    totalFlow += pathFlow;
  }

  return totalFlow;
}