**Write a C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected**

**Program:**

#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:**

Bridges in
first graph

3 4

## No comments:

## Post a Comment