C++ Program to Check whether Graph is Biconnected

Code:

#include    iostream
#include    list
#define NIL -1
using namespace std;

/*
 * Class Declaration
 */
class Graph
{
    private:
        int V;
        list *adj;
        bool isBCUtil(int v, bool visited[], int disc[], int low[],int parent[]);
    public:
        Graph(int V)
        {
            this->V = V;
            adj = new list[V]; 
        }
        void addEdge(int v, int w);
        bool isBC();
};

/*
 * Add Edge to connect v and w
 */
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

/*
 *  A recursive function that returns true if there is an articulation
 *  point in given graph, otherwise returns false
 */
bool Graph::isBCUtil(int u, bool visited[], int disc[],int low[],int parent[])
{

    static int time = 0;
    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = ++time;
    list::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i;
        if (!visited[v])
        {
            children++;
            parent[v] = u;
            if (isBCUtil(v, visited, disc, low, parent))
                return true;
            low[u]  = min(low[u], low[v]);
            if (parent[u] == NIL && children > 1)
                return true;
            if (parent[u] != NIL && low[v] >= disc[u])
                return true;
        }

        else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);
    }
    return false;
}

/*
 * returns true if graph is Biconnected, otherwise false.
 */
bool Graph::isBC()
{
    bool *visited = new bool[V];
    int *disc = new int[V];
    int *low = new int[V];
    int *parent = new int[V];

    for (int i = 0; i < V; i++)
    {
        parent[i] = NIL;
        visited[i] = false;
    }

    if (isBCUtil(0, visited, disc, low, parent) == true)
        return false;

    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            return false;

    return true;
}

/*
 * Main Contains Menu
 */
int main()
{
    Graph g1(2);
    g1.addEdge(0, 1);
    if (g1.isBC())
        cout<<"The Graph is BiConnected"<
    else
        cout<<"The Graph is not BiConnected"<

    Graph g2(5);
    g2.addEdge(1, 0);
    g2.addEdge(0, 2);
    g2.addEdge(2, 1);
    g2.addEdge(0, 3);
    g2.addEdge(3, 4);
    g2.addEdge(2, 4);
    if (g2.isBC())
        cout<<"The Graph is BiConnected"<
    else
        cout<<"The Graph is not BiConnected"<

    Graph g3(3);
    g3.addEdge(0, 1);
    g3.addEdge(1, 2);
    if (g3.isBC())
        cout<<"The Graph is BiConnected"<
    else
        cout<<"The Graph is not BiConnected"<

    Graph g4(5);
    g4.addEdge(1, 0);
    g4.addEdge(0, 2);
    g4.addEdge(2, 1);
    g4.addEdge(0, 3);
    g4.addEdge(3, 4);
    if (g4.isBC())
        cout<<"The Graph is BiConnected"<
    else
        cout<<"The Graph is not BiConnected"<

    Graph g5(3);
    g5.addEdge(0, 1);
    g5.addEdge(1, 2);
    g5.addEdge(2, 0);
    if (g5.isBC())
        cout<<"The Graph is BiConnected"<
    else
        cout<<"The Graph is not BiConnected"<

    return 0;
}


Output:

The Graph is BiConnected
The Graph is BiConnected
The Graph is not BiConnected
The Graph is not BiConnected
The Graph is BiConnected


------------------
(program exited with code: 0)
Press return to continue


More C++ programs: