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

A C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected.

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

A Source Code for the C++ Program to Find Minimum Number of Edges to Cut to make the Graph Disconnected. It's also successfully compiled and run on a Linux system.

#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