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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Algorithm on a Simple Graph

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

DSA C

/* Graph edges: 0-1, 1-2, 2-0, 1-3 */
#include <stdio.h>
#include <stdlib.h>
#define MAX 4

int time_counter = 0;
int disc[MAX], low[MAX];
int visited[MAX];
int parent[MAX];

int graph[MAX][MAX] = {
    {0,1,1,0},
    {1,0,1,1},
    {1,1,0,0},
    {0,1,0,0}
};

void dfs(int u) {
    visited[u] = 1;
    disc[u] = low[u] = ++time_counter;
    for (int v = 0; v < MAX; v++) {
        if (graph[u][v]) {
            if (!visited[v]) {
                parent[v] = u;
                dfs(v);
                if (low[v] > disc[u]) {
                    printf("Bridge found: %d - %d\n", u, v);
                }
                if (low[v] < low[u]) low[u] = low[v];
            } else if (v != parent[u]) {
                if (disc[v] < low[u]) low[u] = disc[v];
            }
        }
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        visited[i] = 0;
        parent[i] = -1;
    }
    for (int i = 0; i < MAX; i++) {
        if (!visited[i]) dfs(i);
    }
    return 0;
}

A No bridges found

B Bridge found: 0 - 1\nBridge found: 1 - 3

C Bridge found: 2 - 0

D Bridge found: 1 - 3

💡 Hint

Focus on edges that, if removed, increase the number of connected components.

The graph has a cycle between nodes 0,1,2, so edges among them are not bridges. The edge 1-3 connects node 3 to the rest, so it's a bridge.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times

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

B The total number of edges connected to the node

C The maximum depth of the node in the DFS tree

D The number of connected components in the graph

💡 Hint

Think about what 'low' helps to detect in the graph.

The 'low' value is the smallest discovery time reachable from the node by following DFS tree edges and back edges.

🔧 Debug

advanced

Identify the Bug in Tarjan's Bridge Detection Code

What is the bug in this snippet of Tarjan's algorithm for bridges? void dfs(int u) { visited[u] = 1; disc[u] = low[u] = ++time_counter; for (int v = 0; v < MAX; v++) { if (graph[u][v]) { if (!visited[v]) { parent[v] = u; dfs(v); if (low[v] >= disc[u]) { printf("Bridge found: %d - %d\n", u, v); } if (low[v] < low[u]) low[u] = low[v]; } else if (v != parent[u]) { if (disc[v] < low[u]) low[u] = disc[v]; } } } }

A The graph adjacency matrix is not symmetric

B The parent array is not initialized before DFS

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

D The visited array is not updated correctly

💡 Hint

Check the condition that identifies bridges carefully.

For bridges, the condition must be 'low[v] > disc[u]'. Using '>=' incorrectly marks edges that are not bridges.

🚀 Application

advanced

Number of Bridges in a Complex Graph

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

A 3

B 2

C 1

D 0

💡 Hint

Look for edges that, if removed, increase the number of connected components.

Edges 0-1 and 1-2 are bridges. The rest form cycles, so no other bridges.

❓ Predict Output

expert

Output of Tarjan's Algorithm on a Disconnected Graph

What is the output of the following code that runs Tarjan's algorithm on a disconnected graph with edges: 0-1, 1-2, 3-4? #include #include #define MAX 5 int time_counter = 0; int disc[MAX], low[MAX]; int visited[MAX]; int parent[MAX]; int graph[MAX][MAX] = { {0,1,0,0,0}, {1,0,1,0,0}, {0,1,0,0,0}, {0,0,0,0,1}, {0,0,0,1,0} }; void dfs(int u) { visited[u] = 1; disc[u] = low[u] = ++time_counter; for (int v = 0; v < MAX; v++) { if (graph[u][v]) { if (!visited[v]) { parent[v] = u; dfs(v); if (low[v] > disc[u]) { printf("Bridge found: %d - %d\n", u, v); } if (low[v] < low[u]) low[u] = low[v]; } else if (v != parent[u]) { if (disc[v] < low[u]) low[u] = disc[v]; } } } } int main() { for (int i = 0; i < MAX; i++) { visited[i] = 0; parent[i] = -1; } for (int i = 0; i < MAX; i++) { if (!visited[i]) dfs(i); } return 0; }

A Bridge found: 1 - 2\nBridge found: 0 - 1\nBridge found: 3 - 4

B Bridge found: 0 - 1\nBridge found: 1 - 2

C Bridge found: 3 - 4

D No bridges found

💡 Hint

Remember to run DFS on all disconnected components.

Edges 0-1 and 1-2 form a chain with no cycles, so both are bridges. Edge 3-4 connects two nodes with no cycle, so it is also a bridge.