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

disc[u] = [1]

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

Atime

B-1

C0

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Setting discovery time to node index instead of time counter.

Initializing discovery time to zero or -1 incorrectly.

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

2fill in blank

medium

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

DSA Python

low[u] = min(low[u], [1])

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

Adisc[v]

Blow[v]

Ctime

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Using discovery time instead of low time for update.

Using the current node's index instead of neighbor's low time.

The low time of a node is updated with the minimum low time of its neighbors.

3fill in blank

hard

Fix the error in the condition that detects a bridge edge in Tarjan's algorithm.

DSA Python

if low[v] [1] disc[u]:
    bridges.append((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 >.

Confusing the order of comparison.

A bridge is found if the low time of neighbor 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 time for back edges.

DSA Python

for v in graph[u]:
    if v == [1]:
        continue
    if disc[v] == -1:
        dfs(v, u)
        low[u] = 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 the edge we came from. After DFS, update low[u] with low[v].

5fill in blank

hard

Fill all three blanks to complete the DFS function header and the initial call.

DSA Python

def dfs([1], [2]):
    global time
    # disc and low initialized outside to -1
    # ... rest of DFS body

# Initialize and start
# disc = [-1] * n
# low = [-1] * n
time = 0
dfs([3], -1)

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

Au

Bparent

Cv

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong parameter names causing confusion.

Not resetting time before DFS.

The DFS function takes current node u and its parent. Arrays disc and low are initialized outside. Start by calling dfs(start, -1) where start is the starting node (e.g., 0).

Practice

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

easy

A. To find the shortest path between two nodes

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

C. To detect cycles in a graph

D. To count the total number of nodes 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: Purpose of Tarjan's algorithm for bridges

   Tarjan's algorithm efficiently finds all such edges (bridges) in a graph 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 if removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Assuming it counts nodes

2. Which of the following is the correct way to initialize the discovery time and low arrays in Tarjan's algorithm in Python?

easy

A. discovery = [-1] * n; low = [-1] * n

B. discovery = [0] * n; low = [0] * n

C. discovery = list(range(n)); low = list(range(n))

D. discovery = None; low = None

Solution

1. Step 1: Understand initialization purpose

   Discovery and low arrays store times; initializing with -1 means unvisited nodes.

2. Step 2: Choose correct initialization

   Using [-1] * n marks all nodes as unvisited initially, which is standard practice.

3. Final Answer:

   discovery = [-1] * n; low = [-1] * n -> Option A

4. Quick Check:

   Unvisited nodes marked with -1 [OK]

Hint: Use -1 to mark unvisited nodes [OK]

Common Mistakes:

• Initializing with zeros (means visited)
• Using range values (incorrect meaning)
• Setting to None (causes errors)

3. What will be the output bridges for the following undirected graph using Tarjan's algorithm?

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2, 4], 4: [3]}

medium

A. []

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

C. [(2, 3), (3, 4)]

D. [(0, 2), (1, 2)]

Solution

1. Step 1: Analyze graph connections

   Nodes 0,1,2 form a triangle (cycle), so no bridges there. Edges (2,3) and (3,4) connect to nodes outside the cycle.

2. Step 2: Identify bridges

   Removing edge (2,3) or (3,4) disconnects the graph, so these are bridges.

3. Final Answer:

   [(2, 3), (3, 4)] -> Option C

4. Quick Check:

   Edges breaking connectivity = bridges [OK]

Hint: Edges outside cycles are likely bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Missing edges connecting components
• Confusing node pairs order

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

def dfs(u, parent):
    visited[u] = True
    disc[u] = time
    low[u] = time
    time += 1
    for v in graph[u]:
        if not visited[v]:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u]:
                bridges.append((u, v))
        elif v != parent:
            low[u] = min(low[u], disc[v])

medium

A. visited array is not updated correctly

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

C. The parent check should be if v == parent, not v != parent

D. time variable is not declared global or passed, causing UnboundLocalError

Solution

1. Step 1: Check variable usage

   The variable 'time' is incremented inside dfs but not declared global or passed, causing an error.

2. Step 2: Understand Python variable scope

   Without 'global time' or passing time as argument, Python treats 'time' as local, causing UnboundLocalError.

3. Final Answer:

   time variable is not declared global or passed, causing UnboundLocalError -> Option D

4. Quick Check:

   Modify time scope to fix error [OK]

Hint: Declare time global or pass as argument [OK]

Common Mistakes:

• Ignoring variable scope errors
• Changing condition operators incorrectly
• Misunderstanding parent node check

5. Given a graph with nodes 0 to 5 and edges:

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. [(3, 4), (4, 5), (5, 3)]

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

D. []

Solution

1. Step 1: Analyze graph structure

   Nodes 0,1,2 form a cycle, so edges among them are not bridges. Nodes 3,4,5 form another cycle.

2. Step 2: Identify connecting edges

   Edge (1,3) connects two cycles. Removing it disconnects the graph, so it is a bridge.

3. Final Answer:

   [(1, 3)] -> Option A

4. Quick Check:

   Bridge connects two cycles [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Including all edges in bridge list
• Ignoring connectivity impact