C++ Program to Check whether Graph is Biconnected or Not

«
»
This C++ Program checks whether Graph is Biconnected.

Here is source code of the C++ Program to check whether Graph is Biconnected. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Check whether Graph is Biconnected
  3.  */
  4. #include <iostream>
  5. #include <list>
  6. #define NIL -1
  7. using namespace std;
  8.  
  9. /*
  10.  * Class Declaration
  11.  */
  12. class Graph
  13. {
  14.     private:
  15.         int V;
  16.         list<int> *adj;
  17.         bool isBCUtil(int v, bool visited[], int disc[], int low[],int parent[]);
  18.     public:
  19.         Graph(int V)
  20.         {
  21.             this->V = V;
  22.             adj = new list<int>[V]; 
  23.         }
  24.         void addEdge(int v, int w);
  25.         bool isBC();
  26. };
  27.  
  28. /*
  29.  * Add Edge to connect v and w
  30.  */
  31. void Graph::addEdge(int v, int w)
  32. {
  33.     adj[v].push_back(w);
  34.     adj[w].push_back(v);
  35. }
  36.  
  37. /*
  38.  *  A recursive function that returns true if there is an articulation
  39.  *  point in given graph, otherwise returns false
  40.  */
  41. bool Graph::isBCUtil(int u, bool visited[], int disc[],int low[],int parent[])
  42. {
  43.  
  44.     static int time = 0;
  45.     int children = 0;
  46.     visited[u] = true;
  47.     disc[u] = low[u] = ++time;
  48.     list<int>::iterator i;
  49.     for (i = adj[u].begin(); i != adj[u].end(); ++i)
  50.     {
  51.         int v = *i;
  52.         if (!visited[v])
  53.         {
  54.             children++;
  55.             parent[v] = u;
  56.             if (isBCUtil(v, visited, disc, low, parent))
  57.                 return true;
  58.             low[u]  = min(low[u], low[v]);
  59.             if (parent[u] == NIL && children > 1)
  60.                 return true;
  61.             if (parent[u] != NIL && low[v] >= disc[u])
  62.                 return true;
  63.         }
  64.  
  65.         else if (v != parent[u])
  66.             low[u]  = min(low[u], disc[v]);
  67.     }
  68.     return false;
  69. }
  70.  
  71. /*
  72.  * returns true if graph is Biconnected, otherwise false.
  73.  */
  74. bool Graph::isBC()
  75. {
  76.     bool *visited = new bool[V];
  77.     int *disc = new int[V];
  78.     int *low = new int[V];
  79.     int *parent = new int[V];
  80.  
  81.     for (int i = 0; i < V; i++)
  82.     {
  83.         parent[i] = NIL;
  84.         visited[i] = false;
  85.     }
  86.  
  87.     if (isBCUtil(0, visited, disc, low, parent) == true)
  88.         return false;
  89.  
  90.     for (int i = 0; i < V; i++)
  91.         if (visited[i] == false)
  92.             return false;
  93.  
  94.     return true;
  95. }
  96.  
  97. /*
  98.  * Main Contains Menu
  99.  */
  100. int main()
  101. {
  102.     Graph g1(2);
  103.     g1.addEdge(0, 1);
  104.     if (g1.isBC())
  105.         cout<<"The Graph is BiConnected"<<endl;
  106.     else
  107.         cout<<"The Graph is not BiConnected"<<endl;
  108.  
  109.     Graph g2(5);
  110.     g2.addEdge(1, 0);
  111.     g2.addEdge(0, 2);
  112.     g2.addEdge(2, 1);
  113.     g2.addEdge(0, 3);
  114.     g2.addEdge(3, 4);
  115.     g2.addEdge(2, 4);
  116.     if (g2.isBC())
  117.         cout<<"The Graph is BiConnected"<<endl;
  118.     else
  119.         cout<<"The Graph is not BiConnected"<<endl;
  120.  
  121.     Graph g3(3);
  122.     g3.addEdge(0, 1);
  123.     g3.addEdge(1, 2);
  124.     if (g3.isBC())
  125.         cout<<"The Graph is BiConnected"<<endl;
  126.     else
  127.         cout<<"The Graph is not BiConnected"<<endl;
  128.  
  129.     Graph g4(5);
  130.     g4.addEdge(1, 0);
  131.     g4.addEdge(0, 2);
  132.     g4.addEdge(2, 1);
  133.     g4.addEdge(0, 3);
  134.     g4.addEdge(3, 4);
  135.     if (g4.isBC())
  136.         cout<<"The Graph is BiConnected"<<endl;
  137.     else
  138.         cout<<"The Graph is not BiConnected"<<endl;
  139.  
  140.     Graph g5(3);
  141.     g5.addEdge(0, 1);
  142.     g5.addEdge(1, 2);
  143.     g5.addEdge(2, 0);
  144.     if (g5.isBC())
  145.         cout<<"The Graph is BiConnected"<<endl;
  146.     else
  147.         cout<<"The Graph is not BiConnected"<<endl;
  148.  
  149.     return 0;
  150. }

advertisement
$ g++ biconnected.cpp
$ a.out
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

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.