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 array in Tarjan's algorithm.

DSA C#

int[] disc = new int[n];
for (int i = 0; i < n; i++) {
    disc[i] = [1];
}

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

An

B0

Cint.MaxValue

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 0 causes confusion with valid discovery times.

We initialize discovery times to -1 to mark nodes as unvisited.

2fill in blank

medium

Complete the code to update the low time of the current node in DFS.

DSA C#

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

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

Alow[v]

Bdisc[v]

Cdisc[u]

Dtime

Attempts:

3 left

💡 Hint

Common Mistakes

Using disc[v] instead of low[v] misses updated low times.

We update low[u] with the minimum low[v] of its neighbors to find back edges.

3fill in blank

hard

Fix the error in the condition to detect a bridge edge.

DSA C#

if (low[v] [1] disc[u]) {
    bridges.Add(new Tuple<int, int>(u, v));
}

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

A<=

B>

C>=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or >= reverses the logic and misses bridges.

A bridge is found when low[v] > disc[u], so the correct condition is low[v] > disc[u].

4fill in blank

hard

Fill both blanks to correctly perform DFS and update low and disc arrays.

DSA C#

disc[u] = low[u] = [1];
time++;
foreach (int v in graph[u]) {
    if (disc[v] == -1) {
        parent[v] = u;
        DFS(v, graph, disc, low, parent, bridges, ref time);
        low[u] = Math.Min(low[u], [2]);
    }
}

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

Atime

Bdisc[v]

Clow[v]

Dparent[u]

Attempts:

3 left

💡 Hint

Common Mistakes

Using disc[v] instead of low[v] for updating low[u].

We set disc[u] and low[u] to current time, then update low[u] with low[v] after DFS call.

5fill in blank

hard

Fill all three blanks to correctly handle back edges in Tarjan's algorithm.

DSA C#

else if (v != [1]) {
    low[u] = Math.Min(low[u], [2]);
    // Back edge found
    if (low[u] == [3]) {
        // Do something
    }
}

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

Aparent[u]

Bdisc[v]

Cdisc[u]

Dparent[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing parent[u] and parent[v] in condition.

We check back edges by ignoring the parent, update low[u] with disc[v], and compare low[u] with disc[u].

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 finds such edges efficiently by using depth-first search 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 bridges with articulation points

2. Which of the following is the correct way to declare the arrays used for discovery and low times in C# for Tarjan's algorithm?

easy

A. int disc = new int[n]; int low = new int[n];

B. int[] disc = new int[n]; int[] low = new int[n];

C. int disc[] = new int[n]; int low[] = new int[n];

D. int[] disc, low = new int[n];

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared as type[] name = new type[size];

2. Step 2: Check each option

   int[] disc = new int[n]; int[] low = new int[n]; uses correct syntax for both arrays. int disc[] = new int[n]; int low[] = new int[n]; uses Java-style syntax, invalid in C#. int disc = new int[n]; int low = new int[n]; misses [] for arrays. int[] disc, low = new int[n]; declares only low as array, disc is just a variable.

3. Final Answer:

   int[] disc = new int[n]; int[] low = new int[n]; -> Option B

4. Quick Check:

   C# arrays = type[] name = new type[size] [OK]

Hint: Use type[] name = new type[size] in C# [OK]

Common Mistakes:

• Using Java array syntax in C#
• Forgetting [] in declaration
• Declaring multiple arrays incorrectly

3. Given the following graph edges and Tarjan's algorithm code snippet, what is the output list of bridges?

Edges: (0-1), (1-2), (2-0), (1-3)

// Assume graph is adjacency list
// Tarjan's algorithm finds bridges

Output bridges:

medium

A. [(0, 1)]

B. [(0, 1), (1, 3)]

C. [(1, 3)]

D. []

Solution

1. Step 1: Analyze the graph structure

   The edges (0-1), (1-2), and (2-0) form a cycle. The edge (1-3) connects node 3 to the cycle.

2. Step 2: Identify bridges

   Edges in a cycle are not bridges because removing them does not disconnect the graph. The edge (1-3) is a bridge because removing it disconnects node 3.

3. Final Answer:

   [(1, 3)] -> Option C

4. Quick Check:

   Only edge (1-3) disconnects graph [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring leaf edges as bridges
• Confusing nodes and edges

4. Identify the bug in this Tarjan's algorithm snippet for finding bridges in C#:

void DFS(int u, int parent) {
  disc[u] = time;
  low[u] = time;
  time++;
  foreach (int v in graph[u]) {
    if (disc[v] == -1) {
      DFS(v, u);
      low[u] = Math.Min(low[u], low[v]);
      if (low[v] > disc[u])
        bridges.Add((u, v));
    } else {
      low[u] = Math.Min(low[u], disc[v]);
    }
  }
}

medium

A. The check 'if (v == parent) continue;' is missing

B. The 'disc[u]' and 'low[u]' are not initialized before DFS

C. The 'time' variable is not incremented correctly

D. The condition 'if (low[v] > disc[u])' should be 'if (low[v] >= disc[u])'

Solution

1. Step 1: Examine the DFS traversal logic

   The code lacks 'if (v == parent) continue;' after foreach. This check prevents processing the parent edge as a back edge, which would incorrectly lower low[u] and miss bridges.

2. Step 2: Rule out other options

   The condition 'if (low[v] > disc[u])' should be 'if (low[v] >= disc[u])': 'low[v] > disc[u]' is correct for bridges (strict >). The 'disc[u]' and 'low[u]' are not initialized before DFS: disc[u] and low[u] are set inside DFS. The 'time' variable is not incremented correctly: time++ follows assignment correctly.

3. Final Answer:

   The check 'if (v == parent) continue;' is missing -> Option A

4. Quick Check:

   Parent check avoids revisiting parent [OK]

Hint: Always skip parent node in DFS to avoid false bridges [OK]

Common Mistakes:

• Forgetting to skip parent node
• Using wrong comparison operator for bridges
• Not initializing discovery times

5. You have a graph with nodes 0 to 5 and edges: (0-1), (1-2), (2-0), (1-3), (3-4), (4-5), (5-3). Using Tarjan's algorithm, which edges are bridges?

hard

A. [(1, 3)]

B. [(1, 3), (3, 4)]

C. [(1, 3), (4, 5)]

D. []

Solution

1. Step 1: Analyze graph cycles and connections

   Edges (0-1), (1-2), (2-0) form a 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; removing it disconnects {0,1,2} from {3,4,5}. Cycle edges like (3-4) are not bridges (path 3-5-4 remains), similarly for others.

3. Final Answer:

   [(1, 3)] -> Option A

4. Quick Check:

   Only edge (1-3) disconnects graph [OK]

Hint: Bridges connect cycles or leaf nodes [OK]

Common Mistakes:

• Missing bridges inside connected components
• Confusing cycle edges as bridges
• Ignoring multi-cycle connections