Cycle Detection in Undirected Graph in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

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

DSA Javascript

function hasCycle(graph) {
  const visited = new Set();
  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true;
      }
    }
    return false;
  }
  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, null)) return true;
    }
  }
  return false;
}

const graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2, 4],
  4: [3]
};

console.log(hasCycle(graph));

A false

B true

C undefined

D TypeError

💡 Hint

Think about whether the graph contains a loop connecting nodes back to an earlier node.

The graph contains a cycle between nodes 0, 1, and 2. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Output of cycle detection using Union-Find

What is the output of the following code that detects a cycle in an undirected graph using Union-Find?

DSA Javascript

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill(0).map((_, i) => i);
    this.rank = Array(size).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false;
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
}

function hasCycle(edges, n) {
  const uf = new UnionFind(n);
  for (const [u, v] of edges) {
    if (!uf.union(u, v)) {
      return true;
    }
  }
  return false;
}

const edges = [[0,1],[1,2],[2,0],[3,4]];
const n = 5;
console.log(hasCycle(edges, n));

A ReferenceError

B false

C true

D undefined

💡 Hint

Check if any union operation fails indicating a cycle.

The edges form a cycle between nodes 0, 1, and 2. The union operation returns false on the third edge, so the function returns true.

🔧 Debug

advanced

Identify the error in cycle detection DFS code

What error does the following code produce when detecting a cycle in an undirected graph?

DSA Javascript

function hasCycle(graph) {
  const visited = new Set();
  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true;
      }
    }
    return false;
  }
  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, null)) return true;
    }
  }
  return false;
}

const graph = {
  0: [1],
  1: [0, 2],
  2: [1]
};

console.log(hasCycle(graph));

A TypeError: Cannot read property 'Symbol(Symbol.iterator)' of undefined

B Maximum call stack size exceeded

C false

D true

💡 Hint

Check the recursive call parameters carefully.

The recursive call dfs(neighbor) misses the parent argument, so inside dfs the parent parameter is undefined, causing graph[undefined] to be accessed, which is undefined, leading to the TypeError when iterating.

❓ Predict Output

advanced

Output of cycle detection on disconnected graph

What is the output of the following code detecting cycles in a disconnected undirected graph?

DSA Javascript

function hasCycle(graph) {
  const visited = new Set();
  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true;
      }
    }
    return false;
  }
  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, null)) return true;
    }
  }
  return false;
}

const graph = {
  0: [1],
  1: [0],
  2: [3],
  3: [2, 4],
  4: [3]
};

console.log(hasCycle(graph));

A TypeError

B true

C undefined

D false

💡 Hint

Check if any component contains a cycle.

The graph has two disconnected components, both are simple chains without cycles, so the function returns false.

🧠 Conceptual

expert

Why does Union-Find detect cycles in undirected graphs?

Why does the Union-Find data structure detect cycles in an undirected graph when a union operation fails?

A Because the two nodes are already connected, so adding an edge creates a loop

B Because the graph is directed and Union-Find tracks directions

C Because Union-Find uses DFS internally to find cycles

D Because Union-Find sorts edges before processing

💡 Hint

Think about what it means if two nodes belong to the same set.

If two nodes are already in the same set, connecting them again creates a cycle. Union-Find detects this by failing the union operation.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we find a node with no neighbors, a cycle exists.

B. If we visit a node that is already visited and is not the parent, a cycle exists.

C. If the graph has more edges than nodes, it always has a cycle.

D. If all nodes are visited exactly once, a cycle exists.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If during DFS, a visited node is found that is not the parent, it means a cycle exists.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option B

4. Quick Check:

   Cycle detection in undirected graph = check visited node not parent [OK]

Hint: Check visited neighbors excluding parent to find cycles [OK]

Common Mistakes:

• Ignoring the parent node in cycle check
• Assuming more edges than nodes always means cycle
• Confusing cycle detection logic with directed graphs

2. Which of the following is the correct way to represent an undirected graph adjacency list in JavaScript?

easy

A. const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]};

B. const graph = [[0,1], [1,2], [2,3]];

C. const graph = {0: 1, 1: 2, 2: 3};

D. const graph = [[1, 2], [0], [0], [1]];

Solution

1. Step 1: Understand adjacency list format

   An adjacency list maps each node to an array of its neighbors.

2. Step 2: Check each option

   const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}; correctly maps nodes to arrays of neighbors. const graph = [[0,1], [1,2], [2,3]]; is edge list, not adjacency list. const graph = {0: 1, 1: 2, 2: 3}; maps nodes to single values, not arrays. const graph = [[1, 2], [0], [0], [1]]; is an array of arrays but connections are not symmetric (node 1 missing neighbor 3).

3. Final Answer:

   const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}; -> Option A

4. Quick Check:

   Adjacency list = node keys with neighbor arrays [OK]

Hint: Adjacency list uses node keys with arrays of neighbors [OK]

Common Mistakes:

• Using edge list instead of adjacency list
• Mapping nodes to single values, not arrays
• Using arrays without keys for adjacency list

3. What will be the output of the following code snippet detecting cycle in an undirected graph?

const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]};

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

const visited = {};
const hasCycle = dfs(0, -1, visited);
console.log(hasCycle);

medium

A. true

B. undefined

C. false

D. TypeError

Solution

1. Step 1: Trace DFS calls and visited nodes

   Start at node 0, mark visited. Visit neighbors 1 and 2. Both lead to nodes without cycles.

2. Step 2: Check for cycle condition

   No neighbor is visited again except parent, so no cycle detected. DFS returns false.

3. Final Answer:

   false -> Option C

4. Quick Check:

   No back edge found = false [OK]

Hint: Cycle if visited neighbor not parent found during DFS [OK]

Common Mistakes:

• Confusing parent node with cycle neighbor
• Assuming any visited node means cycle
• Not initializing visited properly

4. Find the bug in the following cycle detection code for an undirected graph:

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

medium

A. The function should return false inside the for loop.

B. The visited array is not initialized before DFS call.

C. The graph variable is not defined inside the function.

D. The condition 'neighbor === parent' should be 'neighbor !== parent' to detect cycles.

Solution

1. Step 1: Analyze cycle detection condition

   The code returns true if neighbor equals parent, which is incorrect because parent is allowed to be visited.

2. Step 2: Correct condition for cycle detection

   It should return true if neighbor is visited and neighbor is NOT the parent, indicating a cycle.

3. Final Answer:

   The condition 'neighbor === parent' should be 'neighbor !== parent' to detect cycles. -> Option D

4. Quick Check:

   Cycle if visited neighbor not parent [OK]

Hint: Cycle check: visited neighbor must not be parent [OK]

Common Mistakes:

• Returning true when neighbor is parent
• Not initializing visited before DFS
• Returning false too early inside loop

5. Given the undirected graph below, which edges form a cycle?

const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1, 4],
  3: [1],
  4: [2]
};

Select the correct set of edges that create a cycle.

hard

A. Edges (0-1), (1-2), (2-0)

B. Edges (1-3), (3-4), (4-2)

C. Edges (0-2), (2-4), (4-3)

D. Edges (0-1), (1-3), (3-0)

Solution

1. Step 1: Identify cycles by checking connected edges

   Edges (0-1), (1-2), and (2-0) connect nodes in a triangle, forming a cycle.

2. Step 2: Verify other edges

   Edges involving nodes 3 and 4 do not form cycles as they are connected linearly.

3. Final Answer:

   Edges (0-1), (1-2), (2-0) -> Option A

4. Quick Check:

   Triangle edges form cycle [OK]

Hint: Look for triangle or loop edges to find cycles [OK]

Common Mistakes:

• Assuming linear chains form cycles
• Ignoring the triangle formed by nodes 0,1,2
• Confusing edge directions in undirected graph