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.