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.

Practice

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

easy

A. To detect cycles in a graph

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

C. To find the shortest path between two nodes

D. To count the total number of edges in the graph

Solution

1. Step 1: Understand the definition of a bridge

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

2. Step 2: Relate Tarjan's algorithm to bridges

   Tarjan's algorithm efficiently finds such edges by using DFS and low-link values.

3. Final Answer:

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

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph parts when removed [OK]

Common Mistakes:

• Confusing bridges with shortest paths
• Thinking bridges detect cycles
• Assuming bridges count edges

2. Which of the following is the correct way to declare the array that stores discovery times in C for Tarjan's algorithm?

easy

A. int disc = new int[MAX];

B. int disc[];

C. int disc[MAX];

D. int[] disc = new int[MAX];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with type and size like int arr[size];

2. Step 2: Match with discovery time array

   So, int disc[MAX]; is correct for fixed size MAX.

3. Final Answer:

   int disc[MAX]; -> Option C

4. Quick Check:

   C arrays use type name[size] [OK]

Hint: Use type name[size] for arrays in C [OK]

Common Mistakes:

• Using Java or C++ style array declarations in C
• Not specifying array size
• Using dynamic allocation syntax incorrectly

3. Consider the following code snippet for Tarjan's algorithm to find bridges. What will be printed?

void dfs(int u, int parent) {
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u])
        printf("Bridge: %d - %d\n", u, v);
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

// Graph edges:
// 0-1, 1-2, 2-0, 1-3
// Start dfs(0, -1);

medium

A. Bridge: 1 - 3

B. Bridge: 0 - 1

C. Bridge: 2 - 0

D. No bridges

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle 0-1-2 and an edge 1-3. Triangle edges are not bridges because removing them doesn't disconnect the graph.

2. Step 2: Apply Tarjan's condition for bridges

   Edge 1-3 is a bridge because removing it disconnects node 3.

3. Final Answer:

   Bridge: 1 - 3 -> Option A

4. Quick Check:

   Only edge 1-3 disconnects graph [OK]

Hint: Bridges disconnect nodes; triangle edges are safe [OK]

Common Mistakes:

• Thinking all edges in a cycle are bridges
• Ignoring parent check in DFS
• Misinterpreting low and disc values

4. The following code snippet is intended to find bridges using Tarjan's algorithm. What is the bug?

void dfs(int u, int parent) {
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] >= disc[u])
        printf("Bridge: %d - %d\n", u, v);
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

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

B. The disc array is not initialized.

C. The parent parameter is not used correctly.

D. The time variable is not incremented.

Solution

1. Step 1: Understand bridge condition in Tarjan's algorithm

   Bridge condition is low[v] > disc[u], meaning no back edge from v or its descendants to u or above.

2. Step 2: Identify the bug in condition

   Using >= incorrectly marks edges that are not bridges (like parent edges in cycles).

3. Final Answer:

   The condition should be low[v] > disc[u], not >=. -> Option A

4. Quick Check:

   Bridge if low[v] > disc[u] [OK]

Hint: Use strict greater than for bridge check [OK]

Common Mistakes:

• Using >= instead of > in bridge condition
• Not initializing discovery times
• Ignoring parent node in DFS

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

hard

A. [0-1, 2-3]

B. [2-3, 3-4]

C. [1-4]

D. [0-1]

Solution

1. Step 1: Visualize the graph

   Edges: 0-1, 1-2, 2-3, 3-4, 1-4. The edge 1-4 creates a cycle with 1-2-3-4.

2. Step 2: Identify bridges

   Removing 0-1 disconnects node 0, so 0-1 is a bridge. Edges 2-3 and 3-4 are in cycle with 1-4, so not bridges.

3. Final Answer:

   [0-1] -> Option D

4. Quick Check:

   Only 0-1 disconnects graph [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring connectivity after edge removal
• Confusing bridge with articulation point