Bridges in Graph Tarjan's Algorithm in DSA C - 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 C

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

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

A0

Bu

Ctime

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning discovery time to the node index instead of the time counter.

Initializing discovery time to zero or -1 incorrectly.

In Tarjan's algorithm, the discovery time of a node u is set to the current time counter before incrementing it.

2fill in blank

medium

Complete the code to update the low-link value after visiting a neighbor node in Tarjan's algorithm.

DSA C

if (disc[v] != -1) {
    low[u] = [1](low[u], disc[v]);
}

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

Aabs

Bmin

Cmax

Dpow

Attempts:

3 left

💡 Hint

Common Mistakes

Using max instead of min causes incorrect low-link updates.

Using absolute value or power functions incorrectly.

The low-link value of u is updated to the minimum of its current low-link and the discovery time of v if v is already visited.

3fill in blank

hard

Fix the error in the condition that checks if an edge is a bridge in Tarjan's algorithm.

DSA C

if (low[v] [1] disc[u]) {
    printf("Bridge found: %d - %d\n", u, v);
}

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

A<=

B>=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or < instead of > causes false bridge detection.

Using >= includes non-bridge edges.

An edge u-v is a bridge if the low-link value of v is greater than the discovery time of u.

4fill in blank

hard

Fill both blanks to correctly skip the parent node and update low-link after DFS call.

DSA C

for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == [1]) continue;
    if (disc[v] == -1) {
        dfs(v, u);
        low[u] = [2](low[u], low[v]);
    }
}

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

Aparent

Bu

Cmin

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Skipping the wrong node causes infinite loops.

Using max instead of min for low-link update.

The parent node is skipped to avoid revisiting the edge back. After DFS, the low-link of u is updated to the minimum of its current low-link and v's low-link.

5fill in blank

hard

Fill all three blanks to complete the DFS function header and initialize arrays for Tarjan's algorithm.

DSA C

void dfs(int [1], int [2]) {
    disc[[1]] = time;
    low[[1]] = time;
    time++;
    visited[[1]] = true;
    // rest of DFS code
}

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

Au

Bv

Cparent

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing parameter names causes incorrect recursion.

Using inconsistent variable names in arrays.

The DFS function takes the current node u and its parent parent. The discovery and low arrays are updated for u.