Cycle Detection in Directed Graph in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the adjacency list for the graph.

DSA Typescript

const graph: Map<number, number[]> = new Map();
for (let i = 0; i < n; i++) {
  graph.set(i, [1]);
}

Drag options to blanks, or click blank then click option'

A{}

Bnull

C[]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using {} which is an object, not an array.

Using null which causes errors when adding neighbors.

We use an empty array [] to initialize adjacency lists for each node.

2fill in blank

medium

Complete the code to add a directed edge from node u to node v.

DSA Typescript

graph.get(u)![1] v);

Drag options to blanks, or click blank then click option'

A.push(

B.pop(

C.shift(

D.unshift(

Attempts:

3 left

💡 Hint

Common Mistakes

Using .pop() which removes the last element.

Using .shift() or .unshift() which modify the start of the array.

We use .push() to add v to the adjacency list of u.

3fill in blank

hard

Fix the error in the DFS function to mark the current node as visited.

DSA Typescript

function dfs(node: number): boolean {
  visited[node] = true;
  recStack[node] = true;
  for (const neighbor of graph.get(node)!) {
    if (!visited[neighbor] && dfs(neighbor)) {
      return true;
    } else if ([1]) {
      return true;
    }
  }
  recStack[node] = false;
  return false;
}

Drag options to blanks, or click blank then click option'

ArecStack[neighbor]

Bvisited[neighbor]

C!recStack[neighbor]

D!visited[neighbor]

Attempts:

3 left

💡 Hint

Common Mistakes

Checking visited instead of recStack for cycle detection.

Negating recStack[neighbor] which breaks logic.

We check if neighbor is in the recursion stack to detect a cycle.

4fill in blank

hard

Fill both blanks to complete the cycle detection function using DFS.

DSA Typescript

function hasCycle(): boolean {
  visited = new Array(n).fill(false);
  recStack = new Array(n).fill(false);
  for (let i = 0; i < n; i++) {
    if (!visited[i] && [1]) {
      return true;
    }
  }
  return [2];
}

Drag options to blanks, or click blank then click option'

Adfs(i)

Bvisited[i]

Cfalse

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true at the end which incorrectly signals a cycle.

Using visited[i] in the if condition instead of !visited[i].

We call dfs(i) if node i is not visited, and return false if no cycle found.

5fill in blank

hard

Fill all three blanks to create a complete cycle detection using DFS in a directed graph.

DSA Typescript

let visited: boolean[];
let recStack: boolean[];

function detectCycle(n: number, edges: number[][]): boolean {
  const graph: Map<number, number[]> = new Map();
  for (let i = 0; i < n; i++) {
    graph.set(i, [1]);
  }
  for (const [u, v] of edges) {
    graph.get(u)![2] v);
  }
  visited = new Array(n).fill(false);
  recStack = new Array(n).fill(false);
  for (let i = 0; i < n; i++) {
    if (!visited[i] && dfs(i)) {
      return true;
    }
  }
  return [3];
}

Drag options to blanks, or click blank then click option'

A[]

B.push(

Cfalse

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using null instead of [] for adjacency lists.

Using .pop() or other methods instead of .push() to add edges.

Returning true at the end which incorrectly signals a cycle.

Initialize adjacency lists with [], add edges with .push(), and return false if no cycle.

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