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.