Cycle Detection in Undirected 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[]

B0

Cnull

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using an object {} instead of an array for neighbors.

Initializing with null or 0 which are not iterable.

We use an empty array [] to store neighbors for each node.

2fill in blank

medium

Complete the code to add an undirected edge between two nodes u and v.

DSA Typescript

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

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

Agraph

Bv

Cu

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Adding u to u's own list.

Adding graph or null instead of the node number.

We add v to u's neighbors to represent the edge.

3fill in blank

hard

Fix the error in the DFS function to avoid revisiting the parent node.

DSA Typescript

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

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

Anode

Bvisited

Cneighbor

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing neighbor with node instead of parent.

Not checking for parent at all.

We check if the neighbor is not the parent to detect a cycle properly.

4fill in blank

hard

Fill both blanks to complete the cycle detection loop over all nodes.

DSA Typescript

for (let i = 0; i < n; i++) {
  if (!visited[i] && dfs([1], [2])) {
    return true;
  }
}

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

Ai

B0

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as parent which is a valid node and causes wrong cycle detection.

Using null which is not a number.

Start DFS from node i with parent set to -1 (no parent).

5fill in blank

hard

Fill all three blanks to create a function that detects cycles in an undirected graph.

DSA Typescript

function hasCycle(n: number, edges: number[][]): boolean {
  const graph: Map<number, number[]> = new Map();
  const visited: boolean[] = new Array(n).fill(false);

  for (let i = 0; i < n; i++) {
    graph.set(i, [1]);
  }

  for (const [u, v] of edges) {
    graph.get(u)!.push([2]);
    graph.get(v)!.push(u);
  }

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

  for (let i = 0; i < n; i++) {
    if (!visited[i] && dfs(i, [3])) {
      return true;
    }
  }
  return false;
}

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

A[]

Bv

C-1

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Using objects instead of arrays for adjacency lists.

Adding wrong nodes to adjacency lists.

Starting DFS with parent 0 or null instead of -1.

Initialize adjacency lists with empty arrays, add v to u's neighbors, and start DFS with parent -1.