/**
 * Detect cycle in an undirected graph (adjacency list).
 * @param {number} n        — number of nodes (0-indexed)
 * @param {number[][]} edges — list of [u, v] pairs
 * @returns {boolean}
 */
function hasCycleUndirected(n, edges) {
  // Build adjacency list
  const adj = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) {
    adj[u].push(v)
    adj[v].push(u)
  }

  const visited = new Array(n).fill(false)

  function dfs(node, parent) {
    visited[node] = true
    for (const neighbor of adj[node]) {
      if (!visited[neighbor]) {
        if (dfs(neighbor, node)) return true
      } else if (neighbor !== parent) {
        // Visited neighbor that is NOT the parent → back edge → cycle
        return true
      }
    }
    return false
  }

  // Check every connected component
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      if (dfs(i, -1)) return true
    }
  }
  return false
}

// Example
console.log(hasCycleUndirected(4, [[0,1],[1,2],[2,3],[3,1]])) // true  (1-2-3-1)
console.log(hasCycleUndirected(4, [[0,1],[1,2],[2,3]]))        // false (linear chain)

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.rank   = new Array(n).fill(0)
  }

  find(x) {
    // Path compression
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }

  union(x, y) {
    const px = this.find(x)
    const py = this.find(y)
    if (px === py) return false // Already same component → cycle!

    // Union by rank
    if (this.rank[px] < this.rank[py]) this.parent[px] = py
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px
    else { this.parent[py] = px; this.rank[px]++ }

    return true
  }
}

function hasCycleUnionFind(n, edges) {
  const uf = new UnionFind(n)
  for (const [u, v] of edges) {
    if (!uf.union(u, v)) return true // union failed → same root → cycle
  }
  return false
}

console.log(hasCycleUnionFind(4, [[0,1],[1,2],[2,3],[3,1]])) // true
console.log(hasCycleUnionFind(4, [[0,1],[1,2],[2,3]]))        // false

/**
 * Detect cycle in a directed graph.
 * @param {number} n        — number of nodes (0-indexed)
 * @param {number[][]} edges — list of directed edges [from, to]
 * @returns {boolean}
 */
function hasCycleDirected(n, edges) {
  const adj = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) {
    adj[u].push(v)
  }

  // 0 = white (unvisited), 1 = gray (in stack), 2 = black (done)
  const color = new Array(n).fill(0)

  function dfs(node) {
    color[node] = 1 // Mark gray — we are processing this node

    for (const neighbor of adj[node]) {
      if (color[neighbor] === 1) {
        // Reached a gray node → back edge → cycle detected
        return true
      }
      if (color[neighbor] === 0) {
        // White → recurse
        if (dfs(neighbor)) return true
      }
      // Black → already fully explored, skip safely
    }

    color[node] = 2 // Mark black — done with this node
    return false
  }

  for (let i = 0; i < n; i++) {
    if (color[i] === 0) {
      if (dfs(i)) return true
    }
  }
  return false
}

// A → B → C → A  (cycle)
console.log(hasCycleDirected(3, [[0,1],[1,2],[2,0]])) // true

// A → B → C      (no cycle)
console.log(hasCycleDirected(3, [[0,1],[1,2]]))        // false

// A → B → C, A → C (diamond, no cycle)
console.log(hasCycleDirected(3, [[0,1],[1,2],[0,2]])) // false

function hasCycleKahn(n, edges) {
  const adj    = Array.from({ length: n }, () => [])
  const inDeg  = new Array(n).fill(0)

  for (const [u, v] of edges) {
    adj[u].push(v)
    inDeg[v]++
  }

  // Enqueue all nodes with in-degree 0
  const queue = []
  for (let i = 0; i < n; i++) {
    if (inDeg[i] === 0) queue.push(i)
  }

  let processed = 0
  while (queue.length > 0) {
    const node = queue.shift()
    processed++
    for (const neighbor of adj[node]) {
      inDeg[neighbor]--
      if (inDeg[neighbor] === 0) queue.push(neighbor)
    }
  }

  // If we could not process all nodes, a cycle exists
  return processed !== n
}

console.log(hasCycleKahn(3, [[0,1],[1,2],[2,0]])) // true  (cycle)
console.log(hasCycleKahn(4, [[0,1],[1,2],[2,3]])) // false (DAG)

class ListNode {
  constructor(val, next = null) {
    this.val  = val
    this.next = next
  }
}

/**
 * @param {ListNode} head
 * @returns {boolean}
 */
function hasCycle(head) {
  let slow = head
  let fast = head

  while (fast !== null && fast.next !== null) {
    slow = slow.next        // 1 step
    fast = fast.next.next   // 2 steps

    if (slow === fast) return true // They met → cycle exists
  }

  return false // fast reached end → no cycle
}

// Build a list: 1 → 2 → 3 → 4 → 2 (cycle back to node 2)
const n1 = new ListNode(1)
const n2 = new ListNode(2)
const n3 = new ListNode(3)
const n4 = new ListNode(4)
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2 // cycle

console.log(hasCycle(n1)) // true

/**
 * @param {ListNode} head
 * @returns {ListNode|null} — the node where the cycle begins, or null
 */
function detectCycle(head) {
  let slow = head
  let fast = head

  // Phase 1: find meeting point inside the cycle
  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) break
  }

  // No cycle (fast hit null)
  if (fast === null || fast.next === null) return null

  // Phase 2: find cycle start
  // Move one pointer back to head; keep the other at meeting point.
  // Both advance 1 step — they meet at the cycle start.
  let pointer1 = head
  let pointer2 = slow // meeting point

  while (pointer1 !== pointer2) {
    pointer1 = pointer1.next
    pointer2 = pointer2.next
  }

  return pointer1 // cycle start node
}

// 1 → 2 → 3 → 4 → 5 → 3 (cycle at node 3)
const a = new ListNode(1)
const b = new ListNode(2)
const c = new ListNode(3)
const d = new ListNode(4)
const e = new ListNode(5)
a.next = b; b.next = c; c.next = d; d.next = e; e.next = c

const start = detectCycle(a)
console.log(start?.val) // 3

function cycleLength(meetingNode) {
  let current = meetingNode.next
  let length  = 1

  while (current !== meetingNode) {
    current = current.next
    length++
  }

  return length
}

// Uses Union-Find (see full implementation above)
function solve(n, edges) {
  return hasCycleUnionFind(n, edges)
}

console.log(solve(5, [[0,1],[1,2],[3,4],[1,3],[2,4]])) // true

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @returns {boolean}
 */
function canFinish(numCourses, prerequisites) {
  const adj   = Array.from({ length: numCourses }, () => [])
  const color = new Array(numCourses).fill(0) // 0=white, 1=gray, 2=black

  for (const [course, pre] of prerequisites) {
    adj[pre].push(course) // pre → course
  }

  function dfs(node) {
    color[node] = 1 // Mark as being visited (gray)

    for (const next of adj[node]) {
      if (color[next] === 1) return false // Back edge → cycle → can't finish
      if (color[next] === 0 && !dfs(next)) return false
    }

    color[node] = 2 // Fully processed (black)
    return true
  }

  for (let i = 0; i < numCourses; i++) {
    if (color[i] === 0 && !dfs(i)) return false
  }

  return true
}

console.log(canFinish(2, [[1,0]]))        // true  (0→1, no cycle)
console.log(canFinish(2, [[1,0],[0,1]])) // false (0→1→0, cycle)

function findOrder(numCourses, prerequisites) {
  const adj   = Array.from({ length: numCourses }, () => [])
  const inDeg = new Array(numCourses).fill(0)

  for (const [course, pre] of prerequisites) {
    adj[pre].push(course)
    inDeg[course]++
  }

  const queue = []
  for (let i = 0; i < numCourses; i++) {
    if (inDeg[i] === 0) queue.push(i)
  }

  const order = []
  while (queue.length > 0) {
    const cur = queue.shift()
    order.push(cur)
    for (const next of adj[cur]) {
      inDeg[next]--
      if (inDeg[next] === 0) queue.push(next)
    }
  }

  return order.length === numCourses ? order : []
}

console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]])) // [0,1,2,3] or [0,2,1,3]
console.log(findOrder(2, [[0,1],[1,0]]))              // [] (cycle)