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.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. Whether there is a path that starts and ends at the same node following edge directions

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following the direction of edges.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following edge directions -> Option A

4. Quick Check:

   Cycle detection = finding directed loops [OK]

Hint: Cycle means path loops back following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated node without direction

2. Which TypeScript data structure is commonly used to track nodes currently in recursion stack during cycle detection?

easy

A. Queue

B. Array

C. Map

D. Set

Solution

1. Step 1: Identify recursion stack tracking

   We need to quickly check if a node is in the current recursion path.

2. Step 2: Choose data structure for fast membership check

   A Set allows O(1) membership check, ideal for tracking nodes in recursion stack.

3. Final Answer:

   Set -> Option D

4. Quick Check:

   Recursion stack tracking uses Set [OK]

Hint: Use Set for fast membership check in recursion stack [OK]

Common Mistakes:

• Using Array and checking membership with loops (slow)
• Using Queue which is FIFO, not suitable here
• Using Map without key-value need

3. What will be the output of the following TypeScript code snippet detecting cycle in a directed graph?

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

function hasCycle(node: number, visited: Set<number>, recStack: Set<number>): boolean {
  if (!visited.has(node)) {
    visited.add(node);
    recStack.add(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor) && hasCycle(neighbor, visited, recStack)) {
        return true;
      } else if (recStack.has(neighbor)) {
        return true;
      }
    }
  }
  recStack.delete(node);
  return false;
}

console.log(hasCycle(1, new Set(), new Set()));

medium

A. false

B. undefined

C. true

D. Error

Solution

1. Step 1: Analyze graph edges

   Graph edges: 1->2, 2->3, 3->1 form a cycle.

2. Step 2: Trace recursion and cycle detection

   Starting at 1, recursion visits 2, then 3, then back to 1 which is in recursion stack, so returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle exists in 1->2->3->1 path [OK]

Hint: Cycle if recursion stack revisits a node [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle if visited is true
• Confusing visited and recursion stack sets

4. Identify the bug in this TypeScript cycle detection function for a directed graph:

function detectCycle(node: number, visited: Set<number>, recStack: Set<number>): boolean {
  if (visited.has(node)) {
    return false;
  }
  visited.add(node);
  recStack.add(node);
  for (const neighbor of graph.get(node) || []) {
    if (detectCycle(neighbor, visited, recStack)) {
      return true;
    }
  }
  recStack.delete(node);
  return false;
}

medium

A. Missing check if neighbor is in recursion stack to detect cycle

B. Visited set is not updated correctly

C. recStack is never cleared

D. Function does not return boolean

Solution

1. Step 1: Review cycle detection logic

   Cycle detection requires checking if neighbor is already in recursion stack to detect back edge.

2. Step 2: Identify missing condition

   The code calls recursion but does not check if neighbor is in recStack, so misses cycles.

3. Final Answer:

   Missing check if neighbor is in recursion stack to detect cycle -> Option A

4. Quick Check:

   Check recStack for back edges to detect cycles [OK]

Hint: Always check recursion stack for back edges [OK]

Common Mistakes:

• Skipping recursion stack membership check
• Confusing visited and recursion stack roles
• Not removing node from recursion stack after recursion

5. Given a directed graph represented as adjacency list:

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

Which nodes are part of at least one cycle?

hard

A. [1, 2, 4, 6]

B. [3, 5]

C. [2, 4, 6]

D. [1, 3, 5]

Solution

1. Step 1: Analyze edges for cycles

   Edges: 3->5 and 5->3 form a cycle between nodes 3 and 5.

2. Step 2: Check other nodes

   Nodes 1, 2, 4, 6 do not form cycles as no back edges lead to them.

3. Final Answer:

   [3, 5] -> Option B

4. Quick Check:

   Cycle nodes = 3 and 5 only [OK]

Hint: Look for back edges forming loops between nodes [OK]

Common Mistakes:

• Including nodes not in any cycle
• Missing nodes that form cycles
• Confusing path with cycle