Bridges in Graph Tarjan's Algorithm in DSA C# - 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 C# code that uses Tarjan's algorithm to find bridges in an undirected graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;
    int time = 0;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    void BridgeUtil(int u, bool[] visited, int[] disc, int[] low, int[] parent, List<(int,int)> bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time;

        foreach (int v in adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                BridgeUtil(v, visited, disc, low, parent, bridges);
                low[u] = Math.Min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    bridges.Add((u, v));
                }
            } else if (v != parent[u]) {
                low[u] = Math.Min(low[u], disc[v]);
            }
        }
    }

    public List<(int,int)> FindBridges() {
        bool[] visited = new bool[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = -1;

        List<(int,int)> bridges = new List<(int,int)>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                BridgeUtil(i, visited, disc, low, parent, bridges);
            }
        }

        return bridges;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.AddEdge(1, 0);
        g.AddEdge(0, 2);
        g.AddEdge(2, 1);
        g.AddEdge(0, 3);
        g.AddEdge(3, 4);

        var bridges = g.FindBridges();
        foreach (var b in bridges) {
            Console.WriteLine($"{b.Item1} - {b.Item2}");
        }
    }
}

A ["1 - 0", "3 - 4"]

B ["1 - 0", "0 - 2"]

C ["3 - 4", "0 - 3"]

D ["0 - 3", "1 - 2"]

💡 Hint

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

The edges (3,4) and (0,3) are bridges because removing either disconnects the graph. The triangle formed by nodes 0,1,2 has no bridges.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times in Tarjan's Algorithm

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

A The parent node in the DFS tree

B The number of edges connected to the node

C The total number of nodes reachable from the node

D The earliest discovery time reachable from the node including itself and its descendants

💡 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.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Detection Code

What error does the following code snippet cause when run to find bridges in a graph?

DSA C#

void BridgeUtil(int u, bool[] visited, int[] disc, int[] low, int[] parent, List<(int,int)> bridges) {
    visited[u] = true;
    disc[u] = low[u] = ++time;

    foreach (int v in adj[u]) {
        if (!visited[v]) {
            parent[v] = u;
            BridgeUtil(v, visited, disc, low, parent, bridges);
            low[u] = Math.Min(low[u], low[v]);

            if (low[v] >= disc[u]) {
                bridges.Add((u, v));
            }
        } else if (v != parent[u]) {
            low[u] = Math.Min(low[u], disc[v]);
        }
    }
}

A It misses some bridges because it uses '>=' instead of '>' in the condition

B It causes a NullReferenceException due to uninitialized adjacency list

C It causes a stack overflow due to infinite recursion

D It incorrectly identifies some edges as bridges that are not bridges

💡 Hint

Check the condition that decides if an edge is a bridge.

The condition 'if (low[v] >= disc[u])' incorrectly marks edges that are part of cycles as bridges. The correct condition is 'if (low[v] > disc[u])' to identify bridges properly.

🚀 Application

advanced

Number of Bridges in a Complex Graph

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

A 2

B 3

C 1

D 4

💡 Hint

Identify cycles and edges whose removal disconnects the graph.

The cycles are (0,1,2) and (3,4,5). The edges (1-3) and (4-6) are bridges. So total 2 bridges.

❓ Predict Output

expert

Output of Tarjan's Algorithm on a Disconnected Graph

What is the output of the following code that finds bridges in a disconnected graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    int V;
    List<int>[] adj;
    int time = 0;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    void BridgeUtil(int u, bool[] visited, int[] disc, int[] low, int[] parent, List<(int,int)> bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time;

        foreach (int v in adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                BridgeUtil(v, visited, disc, low, parent, bridges);
                low[u] = Math.Min(low[u], low[v]);

                if (low[v] > disc[u]) {
                    bridges.Add((u, v));
                }
            } else if (v != parent[u]) {
                low[u] = Math.Min(low[u], disc[v]);
            }
        }
    }

    public List<(int,int)> FindBridges() {
        bool[] visited = new bool[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = -1;

        List<(int,int)> bridges = new List<(int,int)>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                BridgeUtil(i, visited, disc, low, parent, bridges);
            }
        }

        return bridges;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(7);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(3, 4);
        g.AddEdge(4, 5);
        g.AddEdge(5, 3);
        g.AddEdge(4, 6);

        var bridges = g.FindBridges();
        foreach (var b in bridges) {
            Console.WriteLine($"{b.Item1} - {b.Item2}");
        }
    }
}

A ["0 - 1", "1 - 2"]

B ["4 - 6"]

C []

D ["3 - 4", "4 - 6"]

💡 Hint

Check which edges, when removed, increase the number of connected components.

The cycle (3,4,5) has no bridges. The cycle (0,1,2) has no bridges. The only bridge is edge (4,6).

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