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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Bridge Finding on a Simple Graph

What is the output (list of bridges) of the following C++ code that uses Tarjan's algorithm to find bridges in an undirected graph?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> graph;
vector<int> disc, low;
vector<bool> visited;
int time_counter = 0;
vector<pair<int,int>> bridges;

void dfs(int u, int parent) {
    visited[u] = true;
    disc[u] = low[u] = ++time_counter;
    for (int v : graph[u]) {
        if (v == parent) continue;
        if (!visited[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    int n = 5;
    graph.assign(n, vector<int>());
    disc.assign(n, -1);
    low.assign(n, -1);
    visited.assign(n, false);

    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[4].push_back(3);

    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i, -1);
    }

    sort(bridges.begin(), bridges.end());
    for (auto &b : bridges) {
        cout << b.first << " - " << b.second << "\n";
    }
    return 0;
}

A

1 - 2
1 - 3
3 - 4

B

0 - 1
1 - 2
1 - 3

C

0 - 1
1 - 3
3 - 4

D

0 - 1
1 - 2
3 - 4

💡 Hint

Remember that a bridge is an edge which, if removed, increases the number of connected components.

The edges (0-1), (1-2), (1-3), and (3-4) are bridges because removing any of them disconnects the graph. The code outputs edges (0-1), (1-2), and (3-4) as bridges. Edge (1-3) is also a bridge but depending on DFS traversal order it may appear. The correct bridges are (0-1), (1-2), and (3-4). So the correct answer is C.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times in Tarjan's Algorithm

In Tarjan's algorithm for finding bridges, what does the 'low' value of a node represent?

A The earliest discovery time reachable from the node including itself and its descendants in DFS tree

B The number of edges connected to the node

C The maximum discovery time among all nodes reachable from the node

D The depth of the node in the DFS tree

💡 Hint

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

The 'low' value of a node is the smallest discovery time reachable from that node by following zero or more tree edges and then possibly one back edge. It helps identify if there is a back edge connecting to an ancestor, which is crucial to find bridges.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Detection Code

What is the bug in the following snippet of Tarjan's algorithm for bridges? void dfs(int u, int parent) { visited[u] = true; disc[u] = low[u] = ++time_counter; for (int v : graph[u]) { if (v == parent) continue; if (!visited[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] >= disc[u]) { bridges.push_back({u, v}); } } else { low[u] = min(low[u], disc[v]); } } }

A The condition 'low[v] >= disc[u]' should be 'low[v] > disc[u]' to correctly identify bridges

B The 'visited[u] = true;' line should be after the for loop

C The 'parent' parameter should be ignored when updating low[u]

D The 'disc[u]' should be assigned after the recursive dfs call

💡 Hint

Check the condition that distinguishes bridges from articulation points.

For bridges, the condition is 'low[v] > disc[u]'. Using '>=' incorrectly marks edges that are not bridges. The '>=' condition is used for articulation points, not bridges.

🚀 Application

advanced

Number of Bridges in a Given Graph

Given a graph with 6 nodes and edges: (0-1), (1-2), (2-0), (1-3), (3-4), (4-5), (5-3), how many bridges does Tarjan's algorithm find?

A 3

B 2

C 1

D 0

💡 Hint

Look for edges whose removal increases the number of connected components.

The graph has a triangle (0-1-2) and a cycle (3-4-5). The only bridge is edge (1-3) connecting these two cycles. Removing (1-3) disconnects the graph, so there is exactly 1 bridge.

❓ Predict Output

expert

Output of Tarjan's Algorithm on a Complex Graph

What is the output (list of bridges) of the following C++ code using Tarjan's algorithm on the given graph? Graph edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, 4-6 Code: #include #include #include using namespace std; vector> graph; vector disc, low; vector visited; int time_counter = 0; vector> bridges; void dfs(int u, int parent) { visited[u] = true; disc[u] = low[u] = ++time_counter; for (int v : graph[u]) { if (v == parent) continue; if (!visited[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if (low[v] > disc[u]) { bridges.push_back({min(u,v), max(u,v)}); } } else { low[u] = min(low[u], disc[v]); } } } int main() { int n = 7; graph.assign(n, vector()); disc.assign(n, -1); low.assign(n, -1); visited.assign(n, false); graph[0].push_back(1); graph[1].push_back(0); graph[1].push_back(2); graph[2].push_back(1); graph[2].push_back(0); graph[0].push_back(2); graph[1].push_back(3); graph[3].push_back(1); graph[3].push_back(4); graph[4].push_back(3); graph[4].push_back(5); graph[5].push_back(4); graph[5].push_back(3); graph[3].push_back(5); graph[4].push_back(6); graph[6].push_back(4); for (int i = 0; i < n; i++) { if (!visited[i]) dfs(i, -1); } sort(bridges.begin(), bridges.end()); for (auto &b : bridges) { cout << b.first << " - " << b.second << "\n"; } return 0; }

A

0 - 1
1 - 3
4 - 6

B

1 - 3
4 - 6

C

1 - 3
3 - 4
4 - 6

D

4 - 5
4 - 6

💡 Hint

Identify edges that connect cycles to other parts of the graph.

The graph has two cycles: (0-1-2) and (3-4-5). Edge (1-3) connects these cycles, so (1-3) is a bridge. Edge (4-6) connects node 6 to the cycle, so (4-6) is also a bridge. Edges inside cycles are not bridges. So the bridges are (1-3) and (4-6).

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 the shortest path between two nodes

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

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 the graph.

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

   Tarjan's algorithm efficiently finds such edges by using DFS and tracking discovery and low times.

3. Final Answer:

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

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 edges only

2. Which of the following is the correct way to declare the discovery time array in C++ for Tarjan's bridge-finding algorithm on a graph with n vertices?

easy

A. int disc[n];

B. vector<int> disc(n, -1);

C. int disc = new int[n];

D. int disc[] = new int();

Solution

1. Step 1: Understand C++ array and vector declarations

   Static arrays like int disc[n]; are not standard in C++ (unless n is a constant). Using vector<int> is safer and dynamic.

2. Step 2: Identify correct initialization for discovery times

   Initializing with -1 indicates unvisited nodes, which is common practice.

3. Final Answer:

   vector<int> disc(n, -1); -> Option B

4. Quick Check:

   Use vector with size and initial value [OK]

Hint: Use vector<int> with size and init value [OK]

Common Mistakes:

• Using variable-length arrays (not standard C++)
• Incorrect pointer syntax
• Not initializing discovery times

3. Consider the following C++ code snippet using Tarjan's algorithm to find bridges. What will be the output bridges for the given graph edges?

int n = 4;
vector<int> graph[4];
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
// After running Tarjan's bridge finder, which edges are bridges?
// Edges are represented as pairs (u, v) with u < v

medium

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

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

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

D. []

Solution

1. Step 1: Visualize the graph structure

   The graph is a chain: 0 - 1 - 2 - 3 with bidirectional edges, forming a path with no cycles.

2. Step 2: Apply Tarjan's bridge finding logic

   In a path graph (a tree), every edge is a bridge because removing any disconnects the graph. Tarjan's DFS will detect all three edges where low[v] > disc[u] for each tree edge.

3. Final Answer:

   [(0, 1), (1, 2), (2, 3)] -> Option A

4. Quick Check:

   All edges in path are bridges [OK]

Hint: All edges in chain are bridges [OK]

Common Mistakes:

• Ignoring edge (0,1) as a bridge
• Assuming no bridges in chain
• Confusing bridge with cycle edges

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

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  for (int v : graph[u]) {
    if (v == parent) continue;
    if (!visited[v]) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u])
        bridges.push_back({u, v});
    } else {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

A. Missing initialization of time variable before DFS

B. Incorrect comparison in if condition for bridge detection

C. Not marking nodes as visited

D. Not checking for parent node in adjacency

Solution

1. Step 1: Review the DFS function variables

   The variable 'time' is used to assign discovery times but is not shown initialized before DFS calls.

2. Step 2: Understand impact of uninitialized time

   If 'time' is not initialized to 0 before DFS, discovery and low times will be incorrect, causing wrong bridge detection.

3. Final Answer:

   Missing initialization of time variable before DFS -> Option A

4. Quick Check:

   Initialize time = 0 before DFS [OK]

Hint: Initialize time counter before DFS call [OK]

Common Mistakes:

• Forgetting to initialize time
• Confusing low and disc arrays
• Not skipping parent node in DFS

5. Given a connected undirected graph with n vertices and m edges, how can Tarjan's algorithm be adapted to find all bridges efficiently, and what is its time complexity?

hard

A. Use Dijkstra's algorithm; time complexity O(m log n)

B. Use BFS with distance arrays; time complexity O(n^2)

C. Use DFS without low arrays; time complexity O(m^2)

D. Use DFS with discovery and low arrays; time complexity O(n + m)

Solution

1. Step 1: Describe Tarjan's algorithm adaptation

   Tarjan's algorithm uses DFS traversal, tracking discovery times and low values to detect bridges efficiently.

2. Step 2: Analyze time complexity

   Each vertex and edge is visited once during DFS, so the time complexity is O(n + m), where n is vertices and m is edges.

3. Final Answer:

   Use DFS with discovery and low arrays; time complexity O(n + m) -> Option D

4. Quick Check:

   DFS + low arrays = O(n + m) [OK]

Hint: DFS with low arrays runs in linear time [OK]

Common Mistakes:

• Using BFS which is not suitable here
• Ignoring low arrays in DFS
• Confusing with shortest path algorithms