/**
 * Recursive DFS on an adjacency list
 * @param {Map} graph - adjacency list
 * @param {string|number} start - starting node
 * @returns {Array} nodes in DFS traversal order
 */
function dfsRecursive(graph, start) {
  const visited = new Set();
  const order = [];

  function dfs(node) {
    visited.add(node);
    order.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  dfs(start);
  return order;
}

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'E']],
  ['D', ['B']],
  ['E', ['B', 'C', 'F']],
  ['F', ['E']],
]);

console.log(dfsRecursive(graph, 'A'));
// ['A', 'B', 'D', 'E', 'C', 'F']

/**
 * Iterative DFS using an explicit stack
 * Note: traversal order differs slightly from recursive DFS
 */
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop(); // pop from end (LIFO)

    if (visited.has(node)) continue; // may enqueue same node via different paths

    visited.add(node);
    order.push(node);

    // Push neighbors in reverse so the "first" neighbor is processed first
    const neighbors = graph.get(node) || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }

  return order;
}

console.log(dfsIterative(graph, 'A'));
// ['A', 'B', 'D', 'E', 'C', 'F'] — matches recursive with reverse-push trick

/**
 * Recursive DFS flood-fill on a 2D grid
 * Marks all connected cells with the same value as visited
 */
function dfsGrid(grid, r, c, visited) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  visited[r][c] = true;

  for (const [dr, dc] of dirs) {
    const nr = r + dr;
    const nc = c + dc;

    if (
      nr >= 0 && nr < rows &&
      nc >= 0 && nc < cols &&
      !visited[nr][nc] &&
      grid[nr][nc] === grid[r][c] // same "color" / value
    ) {
      dfsGrid(grid, nr, nc, visited);
    }
  }
}

// Count connected regions of '1'
function countRegions(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let count = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited[r][c]) {
        count++;
        dfsGrid(grid, r, c, visited);
      }
    }
  }

  return count;
}

/**
 * Find all connected components in an undirected graph
 * Returns an array of components, each an array of nodes
 */
function connectedComponents(graph) {
  const visited = new Set();
  const components = [];

  function dfs(node, component) {
    visited.add(node);
    component.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor, component);
      }
    }
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      const component = [];
      dfs(node, component);
      components.push(component);
    }
  }

  return components;
}

const disconnectedGraph = new Map([
  [1, [2, 3]],
  [2, [1]],
  [3, [1]],
  [4, [5]],  // separate component
  [5, [4]],
  [6, []],   // isolated node
]);

console.log(connectedComponents(disconnectedGraph));
// [[1, 2, 3], [4, 5], [6]]

/**
 * DFS with timestamps
 * Useful for: topological sort, SCC detection, cycle detection
 */
function dfsTimestamps(graph) {
  const visited = new Set();
  const discovery = new Map(); // node -> discovery time
  const finish = new Map();    // node -> finish time
  let time = 0;

  function dfs(node) {
    visited.add(node);
    discovery.set(node, ++time); // Record discovery time

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }

    finish.set(node, ++time); // Record finish time
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return { discovery, finish };
}

// Topological sort: nodes in reverse finish-time order
function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    stack.push(node); // push AFTER all descendants are done
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) dfs(node);
  }

  return stack.reverse(); // reverse for correct topological order
}

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let islands = 0;

  function dfs(r, c) {
    // Base cases: out of bounds or water or already sunk
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;

    grid[r][c] = '0'; // Sink the land (mark visited in-place)

    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') {
        islands++;
        dfs(r, c);
      }
    }
  }

  return islands;
}

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1'],
];
console.log(numIslands(grid)); // 3

// Note: modifies the grid in-place. Clone grid first if you need to preserve it.
// Time: O(M*N)  Space: O(M*N) recursive stack in worst case

function validPath(n, edges, source, destination) {
  if (source === destination) return true;

  // Build adjacency list
  const graph = new Map();
  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();

  function dfs(node) {
    if (node === destination) return true;
    visited.add(node);

    for (const neighbor of graph.get(node)) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true; // Short-circuit on first found path
      }
    }

    return false;
  }

  return dfs(source);
}

console.log(validPath(3, [[0,1],[1,2],[2,0]], 0, 2)); // true
console.log(validPath(6, [[0,1],[0,2],[3,5],[5,4],[4,3]], 0, 5)); // false

// Time: O(V+E)  Space: O(V+E)

// Node definition
// function Node(val, neighbors) {
//   this.val = val;
//   this.neighbors = neighbors || [];
// }

function cloneGraph(node) {
  if (!node) return null;

  const cloned = new Map(); // original node -> cloned node

  function dfs(original) {
    if (cloned.has(original)) {
      return cloned.get(original); // Return existing clone (handles cycles!)
    }

    // Create a new node (without neighbors yet)
    const copy = { val: original.val, neighbors: [] };
    cloned.set(original, copy); // Store BEFORE recursing (prevents infinite loops)

    // Recursively clone all neighbors
    for (const neighbor of original.neighbors) {
      copy.neighbors.push(dfs(neighbor));
    }

    return copy;
  }

  return dfs(node);
}

// Example:
// Input graph:  1 -- 2
//               |    |
//               4 -- 3
// Output: deep copy of the same structure

// Time: O(V+E)  Space: O(V) for the cloned map + O(V) recursion stack

function pacificAtlantic(heights) {
  const rows = heights.length;
  const cols = heights[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  const pacific = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => new Array(cols).fill(false));

  // DFS going "uphill" (reverse flow direction)
  function dfs(r, c, visited, prevHeight) {
    if (
      r < 0 || r >= rows ||
      c < 0 || c >= cols ||
      visited[r][c] ||
      heights[r][c] < prevHeight  // Can't flow uphill in reverse = downhill in forward
    ) return;

    visited[r][c] = true;

    for (const [dr, dc] of dirs) {
      dfs(r + dr, c + dc, visited, heights[r][c]);
    }
  }

  // Seed Pacific: top row + left column
  for (let r = 0; r < rows; r++) dfs(r, 0, pacific, heights[r][0]);
  for (let c = 0; c < cols; c++) dfs(0, c, pacific, heights[0][c]);

  // Seed Atlantic: bottom row + right column
  for (let r = 0; r < rows; r++) dfs(r, cols - 1, atlantic, heights[r][cols - 1]);
  for (let c = 0; c < cols; c++) dfs(rows - 1, c, atlantic, heights[rows - 1][c]);

  // Cells reachable by both oceans
  const result = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (pacific[r][c] && atlantic[r][c]) {
        result.push([r, c]);
      }
    }
  }
  return result;
}

const heights = [
  [1,2,2,3,5],
  [3,2,3,4,4],
  [2,4,5,3,1],
  [6,7,1,4,5],
  [5,1,1,2,4],
];
console.log(pacificAtlantic(heights));
// [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

// Time: O(M*N)  Space: O(M*N)

function allPathsSourceTarget(graph) {
  const target = graph.length - 1;
  const result = [];

  function dfs(node, path) {
    if (node === target) {
      result.push([...path]); // Record a copy of the current path
      return;
    }

    for (const neighbor of graph[node]) {
      path.push(neighbor);    // Choose
      dfs(neighbor, path);    // Explore
      path.pop();             // Unchoose (backtrack)
    }
  }

  dfs(0, [0]);
  return result;
}

// graph[i] = list of nodes reachable from node i
const graph = [[1,2],[3],[3],[4],[]]
console.log(allPathsSourceTarget(graph));
// [[0,1,3,4],[0,2,3,4]]

// Visual:
//  0 ---> 1 ---> 3 ---> 4
//  |             ^
//  +-----> 2 ---+

// With backtracking, DFS:
//  - tries 0->1->3->4 ✓ records it
//  - backtracks to 0
//  - tries 0->2->3->4 ✓ records it

// Time: O(2^V * V)  — up to 2^V paths, each up to V long
// Space: O(V)       — recursion depth is at most V (DAG)

// Cycle detection in a DIRECTED graph
function hasCycle(graph) {
  const visited = new Set();
  const recStack = new Set(); // nodes in current DFS path

  function dfs(node) {
    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) return true;
      } else if (recStack.has(neighbor)) {
        return true; // Back edge = cycle!
      }
    }

    recStack.delete(node); // Remove from recursion stack on backtrack
    return false;
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      if (dfs(node)) return true;
    }
  }

  return false;
}

// Cycle detection in an UNDIRECTED graph
function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true; // Visited neighbor that isn't our parent = cycle
      }
    }

    return false;
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      if (dfs(node, -1)) return true;
    }
  }

  return false;
}