C++ Program to Find Number of Articulation Points in a Graph

«
»
This C++ program displays the articulation points present inside a graph. An articulation point inside a graph is the vertex whose removal increases the number of connected components.

Here is the source code of the C++ program to display the nodes which are considered to be articulation points. This C++ program is successfully compiled and run on DevCpp, a C++ compiler.The program output is given below.

  1. /*
  2.  * C++ Program to Find Number of Articulation points in a Graph
  3.  */
  4. #include<iostream>
  5. #include<conio.h>
  6. using namespace std;
  7. int cnt = 0;
  8. struct node_info
  9. {
  10.     int no;
  11. }*q = NULL, *r = NULL;
  12. struct node
  13. {
  14.     node_info *pt;
  15.     node *next;
  16. }*top = NULL, *p = NULL, *np = NULL;
  17. void push(node_info *ptr)
  18. {
  19.     np = new node;
  20.     np->pt = ptr;
  21.     np->next = NULL;
  22.     if (top == NULL)
  23.     {
  24.         top = np;
  25.     }
  26.     else
  27.     {
  28.         np->next = top;
  29.         top = np;
  30.     }
  31. }
  32. node_info *pop()
  33. {
  34.     if (top == NULL)
  35.     {
  36.         cout<<"underflow\n";
  37.     }
  38.     else
  39.     {
  40.         p = top;
  41.         top = top->next;
  42.         return(p->pt);
  43.         delete(p);
  44.     }
  45. }           
  46. int topo(int *v, int am[][7], int i)
  47. {
  48.     q = new node_info;
  49.     q->no = i;
  50.     push(q);
  51.     v[i] = 1;
  52.     for (int j = 0; j < 7; j++)
  53.     {
  54.         if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))
  55.             continue;
  56.         else if(am[i][j] == 1 && v[j] == 0)
  57.         {
  58.             cnt++;
  59.             topo(v, am, j);
  60.         }
  61.     }
  62.     q = pop();
  63. }
  64. void addEdge(int am[][7], int src, int dest)
  65. {
  66.      am[src][dest] = 1;
  67.      am[dest][src] = 1;
  68.      return;
  69. }
  70. int main()
  71. {
  72.     int v[7], am[7][7], amt[7][7], c = 0, a, b, x = 0;
  73.     for (int i = 0; i < 7; i++)
  74.     {
  75.         v[i] = 0;
  76.     }
  77.     for (int i = 0; i < 7; i++)
  78.     {
  79.         for (int j = 0; j < 7; j++)
  80.         {
  81.             am[i][j] = 0;
  82.         }
  83.     }
  84.     while (c < 9)
  85.     {
  86.         cout<<"Enter the source and destination\n";
  87.         cin>>a>>b;
  88.         addEdge(am, a, b);
  89.         c++;
  90.     }
  91.     for (int i = 0; i < 7; i++)
  92.     {
  93.         for (int j = 0; j < 7; j++)
  94.         {
  95.             amt[i][j] = am[i][j];
  96.         }
  97.     }
  98.     for (int i = 0; i < 7; i++)
  99.     {
  100.         for(int j = 0; j < 7; j++)
  101.         {
  102.             am[i][j] = 0;
  103.             am[j][i] = 0;
  104.         }
  105.         if (i < 6)
  106.         {
  107.             topo(v, am, i + 1);
  108.         }
  109.         else
  110.         {
  111.             topo(v, am, 0);
  112.         }
  113.         if (cnt < 5)
  114.         {
  115.             cout<<endl<<i<<" is an articulation point"<<endl;
  116.         }
  117.         cnt = 0;
  118.         for (int j = 0; j < 7; j++)
  119.         {
  120.             am[i][j] = amt[i][j];
  121.             am[j][i] = amt[j][i];
  122.             v[j] = 0;
  123.         }
  124.         while (top != NULL)
  125.         {
  126.               pop();
  127.         }
  128.     }
  129.     getch();
  130. }

advertisement
Output:
 
Enter the source and destination
0
1
Enter the source and destination
0
5
Enter the source and destination
5
4
Enter the source and destination
4
6
Enter the source and destination
0
6
Enter the source and destination
6
2
Enter the source and destination
2
0
Enter the source and destination
3
5
Enter the source and destination
4
3
 
0 is an articulation point

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

Note: Join free Sanfoundry classes at Telegram or Youtube
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.