Bridges in Graph Tarjan's Algorithm in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the discovery time for the current node in Tarjan's algorithm.

DSA Typescript

disc[u] = [1];
low[u] = time;
time += 1;

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

A-1

Bu

Ctime

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting discovery time to 0 or -1 instead of the current time.

Using the node index instead of the time counter.

The discovery time for node u is set to the current time counter before incrementing it.

2fill in blank

medium

Complete the code to update the low value of the current node after visiting a neighbor.

DSA Typescript

low[u] = Math.min(low[u], [1]);

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

Alow[v]

Btime

Cdisc[v]

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Using discovery time of v instead of low[v].

Using the current node u instead of neighbor v.

The low value of u is updated to the minimum between its current low and the low of neighbor v.

3fill in blank

hard

Fix the error in the condition to detect a bridge edge between u and v.

DSA Typescript

if ([1] > disc[u]) {
  bridges.push([u, v]);
}

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

Alow[v]

Bdisc[v]

Clow[u]

Dtime

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing low[u] instead of low[v].

Using disc[v] instead of low[v].

An edge (u, v) is a bridge if low[v] > disc[u], meaning v cannot reach an ancestor of u.

4fill in blank

hard

Fill both blanks to correctly skip the parent node and update low[u] after DFS call.

DSA Typescript

for (const v of graph[u]) {
  if (v === [1]) continue;
  if (disc[v] === -1) {
    dfs(v, u);
    low[u] = Math.min(low[u], [2]);
  }
}

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

Aparent

Bdisc[v]

Clow[v]

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Not skipping the parent node causing infinite recursion.

Updating low[u] with disc[v] instead of low[v].

We skip the parent node to avoid revisiting it, and update low[u] with low[v] after DFS.

5fill in blank

hard

Fill all three blanks to initialize arrays and start DFS for all nodes.

DSA Typescript

const disc: number[] = new Array(n).fill([1]);
const low: number[] = new Array(n).fill([2]);
for (let i = 0; i < n; i++) {
  if (disc[i] === [3]) dfs(i, -1);
}

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

A-1

B0

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing arrays with 0 instead of -1.

Starting DFS on nodes already visited.

Both disc and low arrays are initialized with -1 to mark unvisited nodes, and DFS starts on unvisited nodes.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To sort nodes in topological order

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To find edges that, if removed, increase the number of connected components

Solution

1. Step 1: Understand what a bridge is in a graph

   A bridge is an edge that, when removed, increases the number of connected components in the graph.

2. Step 2: Identify Tarjan's algorithm goal

   Tarjan's algorithm is used to find such edges efficiently by using DFS and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option D

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph if removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Mixing with topological sorting

2. Which of the following is the correct TypeScript syntax to declare the discovery time array for Tarjan's algorithm?

easy

A. let disc = Array(n).fill('undefined');

B. let disc: number = new Array(n);

C. let disc: number[] = new Array(n).fill(-1);

D. let disc: number[] = new Array(n);

Solution

1. Step 1: Understand array declaration with initial values in TypeScript

   To create an array of numbers with size n and initialize all values to -1, use new Array(n).fill(-1).

2. Step 2: Check type correctness

   TypeScript syntax requires disc to be number[] for an array of numbers.

3. Final Answer:

   let disc: number[] = new Array(n).fill(-1); -> Option C

4. Quick Check:

   Array<number> with fill(-1) = correct initialization [OK]

Hint: Use new Array(n).fill(-1) for initialized arrays [OK]

Common Mistakes:

• Using wrong type annotation
• Not initializing array values
• Filling with string instead of number

3. Consider the following TypeScript code snippet using Tarjan's algorithm to find bridges. What will be the output bridges for the given graph?

const graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3]];
// Edges: 0-1, 0-2, 1-2, 2-3, 3-4
// Find bridges
const bridges = findBridges(graph);
console.log(bridges);

medium

A. [[2, 3], [3, 4]]

B. [[0, 1], [1, 2]]

C. [[0, 2], [2, 3]]

D. []

Solution

1. Step 1: Analyze the graph edges and connectivity

   The graph edges are 0-1, 0-2, 1-2 forming a triangle, and 2-3, 3-4 forming a chain. The triangle edges are not bridges because removing one does not disconnect the graph.

2. Step 2: Identify bridges

   Edges 2-3 and 3-4 are bridges because removing either disconnects node 4 or node 3 from the rest.

3. Final Answer:

   [[2, 3], [3, 4]] -> Option A

4. Quick Check:

   Bridges disconnect graph = [[2,3],[3,4]] [OK]

Hint: Bridges are edges not in any cycle [OK]

Common Mistakes:

• Including edges inside cycles as bridges
• Missing chain edges as bridges
• Confusing node indices

4. The following TypeScript function attempts to find bridges using Tarjan's algorithm but has a bug. What is the bug?

function dfs(u: number, parent: number) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  for (const v of graph[u]) {
    if (!visited[v]) {
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) {
        bridges.push([u, v]);
      }
    } else if (v !== parent) {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

medium

A. The condition 'low[v] > disc[u]' should be 'low[v] >= disc[u]'

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

C. The 'time' variable is not incremented correctly

D. The parent node check 'v !== parent' is missing

Solution

1. Step 1: Check initialization of visited array

   The code uses 'visited[u]' but does not show initialization. Without initializing, visited may be undefined causing runtime errors.

2. Step 2: Verify other parts

   The condition 'low[v] > disc[u]' is correct for bridges. The parent check is present. The time increment is correct.

3. Final Answer:

   The 'visited' array is not initialized before DFS -> Option B

4. Quick Check:

   Uninitialized visited array causes errors [OK]

Hint: Always initialize visited before DFS [OK]

Common Mistakes:

• Changing correct bridge condition
• Ignoring visited initialization
• Removing parent check

5. Given a connected undirected graph with nodes 0 to 5 and edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, which edges are bridges according to Tarjan's algorithm?

hard

A. [[1, 3]]

B. [[3, 4], [4, 5]]

C. [[0, 1], [1, 2]]

D. []

Solution

1. Step 1: Analyze graph structure

   Edges 0-1, 1-2, 2-0 form a triangle (cycle). Edges 3-4, 4-5, 5-3 form another cycle. Edge 1-3 connects these two cycles.

2. Step 2: Identify bridges

   Only edge 1-3 is a bridge because removing it disconnects the two cycles. Other edges are part of cycles and not bridges.

3. Final Answer:

   [[1, 3]] -> Option A

4. Quick Check:

   Bridge connects two cycles = [[1, 3]] [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Missing the connecting bridge edge
• Confusing node pairs