Given a undirected connected graph, check if the graph is 2-edge connected or not.

A connected graph is 2-edge-connected if it remains connected whenever any edges is removed. A bridge or cut arc is an edge of a graph whose deletion increases its number of connected components. i.e. whose removal disconnects the graph. So if any such bridge exists, the graph is not 2-edge-connected.

For example,

Below graph has 6 vertices and 3 bridges (highlighted in red)

**Prerequisite:**

1. Types of edges involved in DFS and relation between them

2. Arrival and Departure Time of Vertices in DFS

A simple approach is to remove each edge from the graph one by one and run DFS or BFS starting from any vertex. If the DFS or BFS covers all nodes in the graph, then the removed edge cannot be a bridge. If not, that edge is bridge. The time complexity of above solution is `O(E(V + E))` where V is number of vertices and E is number of edges in the graph.

We can solve this problem efficiently in one pass of DFS. When we do a DFS from vertex v in an undirected graph, there could be edges which are going out of the sub tree i.e back edges. We can say that the graph is 2-edge connected if and only if **for every edge u->v in the graph, there is at-least one back-edge that is going out of subtree rooted at v to some ancestor of u.** When we say subtree rooted at v, we mean all v’s descendants including the vertex itself.

In other words, when we backtrack from a vertex v, we need to ensure that there is some back-edge from some descendant of v (including v) to some proper ancestor(parent or above) of v.

**How should we modify DFS so that we can check if there is a back-edge going out of every sub tree?**

We can modify DFS such that `DFS(v)`

returns the smallest arrival time to which there is an back edge from the sub tree rooted at v. For example, let `arrival(v)` be the arrival time of vertex v in the DFS. Then if there is a back out of the sub tree rooted at v, it’s to something visited before v & therefore with a smaller arrival value. Remember for a back edge `u -> v`

in a graph,

arrival[u] > arrival[v]

Suppose there are four edges going out of sub-tree rooted at v to vertex a, b, c and d and with arrival time `A(a), A(b), A(c)` and `A(d)` respectively. We look at their four arrival times & consider the smallest among them and that will be the value returned by `DFS(v)`. i.e. `DFS(v)` returns min of `A(a), A(b), A(c)` and `A(d)`. But before returning, we have to check that `min (A(a), A(b), A(c), A(d))` is less than the `A(v)`. If `min(A(a), A(b), A(c), A(d))` is less than the `A(v)`, then that means that at-least one back-edge is going out of the sub tree rooted at v. If not, we can say that `(parent[v], v)` is a bridge.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // data structure to store graph edges struct Edge { int src, dest; }; class Graph { public: // construct a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the undirected graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Perform DFS on graph starting from vertex v and find // all Bridges in the process int DFS(Graph const &graph, int v, vector<bool> discovered, int arrival[], int parent, int &time) { // set arrival time of vertex v arrival[v] = ++time; // mark vertex as discovered discovered[v] = true; // initialize arr to arrival time of vertex v int arr = arrival[v]; // (v, w) forms a edge for (int w : graph.adjList[v]) { // w is not discovered if (!discovered[w]) { arr = min(arr, DFS(graph, w, discovered, arrival, v, time)); // w is discovered and w is not parent of v } else if (w != parent) { // If the vertex w is already discovered, that // means that there is a back edge starting // from v. Note that as discovered[u] is already // true, arrival[u] is already defined arr = min(arr, arrival[w]); } } // if value of arr remains unchanged i.e. it is equal // to the arrival time of vertex v and if v is not root // node, then (parent[v] -> v) forms a Bridge if (arr == arrival[v] && parent != -1) cout << parent << ", " << v << '\n'; // we return the minimum arrival time return arr; } // 2-Edge Connectivity in a Graph int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 2}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {3, 5} }; // Number of nodes in the graph int N = 10; // create a graph from edges Graph graph(edges, N); // stores vertex is discovered or not vector<bool> discovered(N); // stores arrival time of a node in DFS int arrival[N]; int start = 0, parent = -1, time = 0; // As given graph is connected, DFS will cover every node DFS(graph, start, discovered, arrival, parent, time); return 0; } |

`Output:`

2, 1

3, 5

0, 2

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
import java.util.*; // data structure to store graph edges class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } }; // class to represent a graph object class Graph { // An array of Lists to represent adjacency list List<List<Integer>> adjList = null; // Constructor Graph(List<Edge> edges, int N) { adjList = new ArrayList<>(N); for (int i = 0; i < N; i++) { adjList.add(i, new ArrayList<>()); } // add edges to the undirected graph for (int i = 0; i < edges.size(); i++) { int src = edges.get(i).source; int dest = edges.get(i).dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class EdgeConnectivity { // Perform DFS on graph starting from vertex v and find // all Bridges in the process public static int DFS(Graph graph, int v, boolean[] discovered, int[] arrival, int parent, int time) { // set arrival time of vertex v arrival[v] = ++time; // mark vertex as discovered discovered[v] = true; // initialize arr to arrival time of vertex v int arr = arrival[v]; // (v, w) forms a edge for (int w: graph.adjList.get(v)) { // w is not discovered if (!discovered[w]) arr = Integer.min(arr, DFS(graph, w, discovered, arrival, v, time)); // w is discovered and w is not parent of v else if (w != parent) // If the vertex w is already discovered, that // means that there is a back edge starting // from v. Note that as discovered[u] is already // true, arrival[u] is already defined arr = Integer.min(arr, arrival[w]); } // if value of arr remains unchanged i.e. it is equal // to the arrival time of vertex v and if v is not root // node, then (parent[v] -> v) forms a Bridge if (arr == arrival[v] && parent != -1) System.out.println(parent + ", " + v); // we return the minimum arrival time return arr; } public static void main(String[] args) { // initialize edges as per above diagram // (u, v, w) triplet represent undirected edge from // vertex u to vertex v having weight w List<Edge> edges = Arrays.asList( new Edge(0, 2), new Edge(1, 2), new Edge(2, 3), new Edge(2, 4), new Edge(3, 4), new Edge(3, 5) ); // Number of vertices in the graph final int N = 6; // construct graph Graph graph = new Graph(edges, N); // stores vertex is discovered or not boolean[] discovered = new boolean[N]; // stores arrival time of a node in DFS int[] arrival = new int[N]; int start = 0, parent = -1, time = 0; // As given graph is connected, DFS will cover every node DFS(graph, start, discovered, arrival, parent, time); } } |

`Output:`

2, 1

3, 5

0, 2

*Please note that the same edges might end up printed twice. We can use a std::map avoid that with key as vertex number and value as std::set. i.e. std::map<int, set<int>>.*

The time complexity of above solution is `O(n + m)` where n is number of vertices and m is number of edges in the graph.

**Reference:** Dr. Naveen garg, IIT-D (Lecture – 28 Applications of DFS)

**Image credits:** http://mathworld.wolfram.com/GraphBridge.html

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply