Bridges in Graph Tarjan's Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Algorithm for Bridges

What is the output (list of bridges) of the following Tarjan's algorithm code when run on the given graph?

DSA Python

def find_bridges(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    time = 0
    disc = [-1] * n
    low = [-1] * n
    bridges = []

    def dfs(u, parent):
        nonlocal time
        disc[u] = time
        low[u] = time
        time += 1
        for v in graph[u]:
            if disc[v] == -1:
                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])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return sorted(bridges)

n = 5
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]
print(find_bridges(n, edges))

A [(2, 0), (1, 3)]

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

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

D [(0, 1), (2, 0), (3, 4)]

💡 Hint

Look for edges where the low time of the connected node is greater than the discovery time of the current node.

Edges (1, 3) and (3, 4) are bridges because removing them increases the number of connected components. The triangle formed by nodes 0, 1, 2 has no bridges.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times

In Tarjan's algorithm for finding bridges, what does the 'low' array represent?

A The earliest discovery time reachable from the node including back edges

B The number of edges connected to the node

C The time when the node was first visited

D The parent node in the DFS tree

💡 Hint

Think about how 'low' helps detect cycles and back edges.

The 'low' value of a node is the smallest discovery time reachable from that node by following DFS tree edges and back edges. It helps identify if a node can reach an ancestor, which is key to finding bridges.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Code

What error will occur when running this modified Tarjan's algorithm code?

DSA Python

def find_bridges(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    time = 0
    disc = [-1] * n
    low = [-1] * n
    bridges = []

    def dfs(u, parent):
        disc[u] = time
        low[u] = time
        time += 1
        for v in graph[u]:
            if disc[v] == -1:
                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])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return sorted(bridges)

A No error, runs correctly

B IndexError: list index out of range

C TypeError: unsupported operand type(s) for +: 'int' and 'str'

D UnboundLocalError: local variable 'time' referenced before assignment

💡 Hint

Check how the variable 'time' is used inside the dfs function.

The variable 'time' is assigned inside dfs without declaring it as nonlocal, causing Python to treat it as local and raising UnboundLocalError when incremented.

🚀 Application

advanced

Number of Bridges in a Complete Graph

If you run Tarjan's algorithm to find bridges on a complete graph with 4 nodes (every node connected to every other), how many bridges will it find?

A 0

B 3

C 6

D 4

💡 Hint

Think about whether removing any edge disconnects the graph.

In a complete graph, every node is connected to every other node directly. Removing any single edge does not disconnect the graph, so there are no bridges.

❓ Predict Output

expert

Output of Tarjan's Algorithm on a Complex Graph

What is the output (list of bridges) of the following Tarjan's algorithm code when run on the given graph?

DSA Python

def find_bridges(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    time = 0
    disc = [-1] * n
    low = [-1] * n
    bridges = []

    def dfs(u, parent):
        nonlocal time
        disc[u] = time
        low[u] = time
        time += 1
        for v in graph[u]:
            if disc[v] == -1:
                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])

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return sorted(bridges)

n = 7
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (4, 6)]
print(find_bridges(n, edges))

A [(0, 1), (1, 3), (4, 6)]

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

C [(3, 4), (4, 6)]

D [(1, 3), (3, 4), (4, 6)]

💡 Hint

Check which edges connect components that would disconnect if removed.

Edges (1, 3) and (4, 6) are bridges. The cycle between nodes 3, 4, 5 has no bridges.

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