Cycle Detection in Directed Graph in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

What is the output of the following TypeScript code that detects a cycle in a directed graph using DFS?

DSA Typescript

function hasCycle(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  const recStack = new Set<number>();

  function dfs(node: number): boolean {
    if (!visited.has(node)) {
      visited.add(node);
      recStack.add(node);

      for (const neighbor of graph.get(node) || []) {
        if (!visited.has(neighbor) && dfs(neighbor)) {
          return true;
        } else if (recStack.has(neighbor)) {
          return true;
        }
      }
    }
    recStack.delete(node);
    return false;
  }

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

const graph = new Map<number, number[]>([
  [1, [2]],
  [2, [3]],
  [3, [4]],
  [4, [2]]
]);

console.log(hasCycle(graph));

A true

B false

C undefined

D SyntaxError

💡 Hint

Think about whether the graph has a back edge that forms a cycle.

The graph has edges 1→2, 2→3, 3→4, and 4→2. The edge 4→2 creates a cycle involving nodes 2, 3, and 4. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Output of cycle detection with no cycles

What is the output of the following TypeScript code that checks for cycles in a directed graph with no cycles?

DSA Typescript

function detectCycle(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  const recStack = new Set<number>();

  function dfs(node: number): boolean {
    if (!visited.has(node)) {
      visited.add(node);
      recStack.add(node);

      for (const neighbor of graph.get(node) || []) {
        if (!visited.has(neighbor) && dfs(neighbor)) {
          return true;
        } else if (recStack.has(neighbor)) {
          return true;
        }
      }
    }
    recStack.delete(node);
    return false;
  }

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

const graph = new Map<number, number[]>([
  [1, [2]],
  [2, [3]],
  [3, [4]],
  [4, []]
]);

console.log(detectCycle(graph));

A TypeError

B true

C null

D false

💡 Hint

Check if any node revisits a node in the current recursion stack.

The graph edges are 1→2, 2→3, 3→4, and 4 has no outgoing edges. There is no cycle, so the function returns false.

🧠 Conceptual

advanced

Understanding recursion stack in cycle detection

In cycle detection for a directed graph using DFS, what is the main purpose of the recursion stack (recStack)?

A To keep track of all visited nodes globally

B To store nodes that have no outgoing edges

C To store nodes currently in the path of DFS to detect back edges

D To count the total number of nodes in the graph

💡 Hint

Think about how cycles are detected during DFS traversal.

The recursion stack keeps track of nodes currently being explored in the current DFS path. If a node is revisited while still in this stack, it means a cycle exists (a back edge).

🔧 Debug

advanced

Identify the error in cycle detection code

What error will the following TypeScript code produce when detecting cycles in a directed graph?

DSA Typescript

function checkCycle(graph: Map<number, number[]>): boolean {
  const visited = new Set<number>();
  const recStack = new Set<number>();

  function dfs(node: number): boolean {
    if (visited.has(node)) {
      return false;
    }
    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor) && dfs(neighbor)) {
        return true;
      } else if (recStack.has(neighbor)) {
        return true;
      }
    }
    recStack.delete(node);
    return false;
  }

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

const graph = new Map<number, number[]>([
  [1, [2]],
  [2, [3]],
  [3, [1]]
]);

console.log(checkCycle(graph));

A The code runs and outputs true

B The code runs and outputs false

C Stack overflow error due to infinite recursion

D TypeError due to undefined property access

💡 Hint

Check how visited nodes are handled in the DFS function.

The code incorrectly returns false immediately if a node is visited, without checking if it is in the recursion stack. This causes it to miss cycles and return false even when a cycle exists.

🚀 Application

expert

Number of cycles in a directed graph

Given the following directed graph represented as adjacency list, how many distinct cycles does it contain?

DSA Typescript

const graph = new Map<number, number[]>([
  [1, [2, 3]],
  [2, [4]],
  [3, [2]],
  [4, [1, 5]],
  [5, []]
]);

A 2

B 1

C 3

D 0

💡 Hint

Trace paths and look for cycles formed by back edges.

The graph contains two cycles: 1→2→4→1 and 1→3→2→4→1. Both are distinct cycles involving different paths.