Programming Assignment 4 Solution

Problem 1. Given an undirected graph G, a bridge is an edge of the graph that if removed disconnects the graph. A separating vertex (also called articulation point) is a vertex of the graph, which if removed, disconnects the graph. Equivalently, an edge is not a bridge i it lies on some cycle. Figure 1 gives an example. In this gure, vertices d; a; h and l are separating vertices. Note that k is not a separating vertex. The edges fe; hg and fk; lg are bridges.




Given an undirected graph G as input in adjacency list format, print all the bridges and articulation points of G.























































Figure 1: An example graph


















































































1