This is a C++ Program to find minimum number of edges to cut to make the graph disconnected. An edge in an undirected connected graph is a bridge if removing it disconnects the graph. For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components.

Here is source code of the C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`// A C++ program to find bridges in a given undirected graph`

`#include<iostream>`

`#include <list>`

`#define NIL -1`

using namespace std;

`// A class that represents an undirected graph`

`class Graph`

`{`

int V; // No. of vertices

list<int> *adj; // A dynamic array of adjacency lists

void bridgeUtil(int v, bool visited[], int disc[], int low[],

int parent[]);

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

void bridge(); // prints all bridges

};

Graph::Graph(int V)

`{`

this->V = V;

adj = new list<int> [V];

`}`

void Graph::addEdge(int v, int w)

`{`

adj[v].push_back(w);

adj[w].push_back(v); // Note: the graph is undirected

`}`

void Graph::bridgeUtil(int u, bool visited[], int disc[], int low[],

int parent[])

`{`

`// A static variable is used for simplicity, we can avoid use of static`

`// variable by passing a pointer.`

static int time = 0;

`// Mark the current node as visited`

visited[u] = true;

`// Initialize discovery time and low value`

disc[u] = low[u] = ++time;

`// Go through all vertices aadjacent to this`

list<int>::iterator i;

for (i = adj[u].begin(); i != adj[u].end(); ++i)

`{`

int v = *i; // v is current adjacent of u

`// If v is not visited yet, then recur for it`

if (!visited[v])

`{`

parent[v] = u;

bridgeUtil(v, visited, disc, low, parent);

`// Check if the subtree rooted with v has a connection to`

`// one of the ancestors of u`

low[u] = min(low[u], low[v]);

`// If the lowest vertex reachable from subtree under v is`

`// below u in DFS tree, then u-v is a bridge`

if (low[v] > disc[u])

cout << u << " " << v << endl;

`}`

`// Update low value of u for parent function calls.`

else if (v != parent[u])

low[u] = min(low[u], disc[v]);

`}`

`}`

`// DFS based function to find all bridges. It uses recursive function bridgeUtil()`

void Graph::bridge()

`{`

`// Mark all the vertices as not visited`

bool *visited = new bool[V];

int *disc = new int[V];

int *low = new int[V];

int *parent = new int[V];

`// Initialize parent and visited arrays`

for (int i = 0; i < V; i++)

`{`

parent[i] = NIL;

visited[i] = false;

`}`

`// Call the recursive helper function to find Bridges`

`// in DFS tree rooted with vertex 'i'`

for (int i = 0; i < V; i++)

if (visited[i] == false)

bridgeUtil(i, visited, disc, low, parent);

`}`

`// Driver program to test above function`

int main()

`{`

`// Create graphs given in above diagrams`

cout << "\nBridges in first graph \n";

Graph g1(5);

g1.addEdge(1, 0);

g1.addEdge(0, 2);

g1.addEdge(2, 1);

g1.addEdge(0, 3);

g1.addEdge(3, 4);

g1.bridge();

cout << "\nBridges in second graph \n";

Graph g2(4);

g2.addEdge(0, 1);

g2.addEdge(1, 2);

g2.addEdge(2, 3);

g2.bridge();

cout << "\nBridges in third graph \n";

Graph g3(7);

g3.addEdge(0, 1);

g3.addEdge(1, 2);

g3.addEdge(2, 0);

g3.addEdge(1, 3);

g3.addEdge(1, 4);

g3.addEdge(1, 6);

g3.addEdge(3, 5);

g3.addEdge(4, 5);

g3.bridge();

return 0;

`}`

Output:

`$ g++ Bridges.cpp`

$ a.out
Bridges in first graph

3 4