C++ Program to Find Strongly Connected Components in Graphs

This C++ program displays the nodes which are strongly connected to each other. Strongly connected subgraphs are those in which a path is available from any node of the subgraph to any other node present in it.

Here is the source code of the C++ program to display the set of strongly connected components. 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 Strongly Connected Components in Graphs
  3.  */
  4. #include<iostream>
  5. #include<conio.h>
  6. using namespace std;
  7. struct node_info
  8. {
  9.     int no;
  10.     int lv_time, st_time;
  11. }*q = NULL;
  12. struct node
  13. {
  14.     node_info *pt;
  15.     node *next;
  16. }*top = NULL, *p = NULL, *np = NULL;
  17. struct node1
  18. {
  19.     node1 *link;
  20.     node_info *pt1;
  21. }*head = NULL, *m = NULL, *n = NULL, *np1 = NULL;
  22. int c = 0;
  23. void push(node_info *ptr)
  24. {
  25.     np = new node;
  26.     np->pt = ptr;
  27.     np->next = NULL;
  28.     if (top == NULL)
  29.     {
  30.         top = np;
  31.     }
  32.     else
  33.     {
  34.         np->next = top;
  35.         top = np;
  36.     }
  37. }
  38. node_info *pop()
  39. {
  40.     if (top == NULL)
  41.     {
  42.         cout<<"underflow\n";
  43.     }
  44.     else
  45.     {
  46.         p = top;
  47.         top = top->next;
  48.         return(p->pt);
  49.         delete(p);
  50.     }
  51. }
  52. void store(node_info *ptr1)
  53. {
  54.     np1 = new node1;
  55.     np1->pt1 = ptr1;
  56.     np1->link = NULL;
  57.     if (c == 0)
  58.     {
  59.         head = np1;
  60.         m = head;
  61.         m->link = NULL;
  62.         c++;
  63.     }
  64.     else
  65.     {
  66.         m = head;
  67.         np1->link = m;
  68.         head = np1;
  69.     }
  70. }
  71. void remove(int x)
  72. {
  73.     m = head;
  74.     if ((m->pt1)->no == x)
  75.     {
  76.         head = head->link;
  77.         delete(m);
  78.     }
  79.     else
  80.     {
  81.         while ((m->pt1)->no != x && m->link != NULL)
  82.         {
  83.             n = m;
  84.             m = m->link;
  85.         }
  86.         if ((m->pt1)->no == x)
  87.         {
  88.             n->link = m->link;
  89.             delete(m);
  90.         }
  91.         else if (m->link == NULL)
  92.         {
  93.             cout<<"error\n";
  94.         }
  95.     }
  96. }            
  97. void topo(int *v, int am[][8], int i)
  98. {
  99.     q = new node_info;
  100.     q->no = i;
  101.     q->st_time = c;
  102.      push(q);
  103.     v[i] = 1;
  104.     for (int j = 0; j < 8; j++)
  105.     {
  106.         if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))
  107.             continue;
  108.         else if (am[i][j] == 1 && v[j] == 0)
  109.         {
  110.             c++;
  111.             topo(v,am,j);
  112.         }
  113.     }
  114.     c++;
  115.     q = pop();
  116.     q->lv_time = c;
  117.     store(q);
  118.     return;
  119. }
  120. void topo1(int *v, int am[][8], int i)
  121. {
  122.     v[i] = 1;
  123.     remove(i);
  124.     cout<<i<<endl;
  125.     for (int j = 0; j < 8; j++)
  126.     {
  127.         if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))
  128.         {
  129.             continue;
  130.         }
  131.         else if (am[i][j] == 1 && v[j] == 0)
  132.         {
  133.             topo1(v,am,j);
  134.         }
  135.     }
  136.     return;
  137. }
  138. int main()
  139. {
  140.     int v[8], am[8][8], amt[8][8];
  141.     for (int i = 0; i < 8; i++)
  142.         v[i] = 0;
  143.     for (int i = 0; i < 8; i++)
  144.     {
  145.         cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;
  146.         for (int j = 0; j < 8; j++)
  147.         {
  148.             cin>>am[i][j];
  149.         }
  150.     }
  151.     topo(v, am, 0);
  152.     for (int i = 0; i < 8; i++)
  153.     {
  154.         v[i] = 0;
  155.         for (int j = 0; j < 8; j++)
  156.             amt[j][i] = am[i][j];
  157.     }
  158.     while (head != NULL)
  159.     {
  160.         cout<<"Strongly Connected Components:\n";                 
  161.             topo1(v, amt, (head->pt1)->no);
  162.     }
  163.     getch();
  164. }

 
Output
 
enter the values for adjacency matrix row:1
0
1
0
0
0
0
0
0
enter the values for adjacency matrix row:2
0
0
1
0
1
1
0
0
enter the values for adjacency matrix row:3
0
0
0
1
0
0
1
0
enter the values for adjacency matrix row:4
0
0
1
0
0
0
0
1
enter the values for adjacency matrix row:5
1
0
0
0
0
1
0
0
enter the values for adjacency matrix row:6
0
0
0
0
0
0
1
0
enter the values for adjacency matrix row:7
0
0
0
0
0
1
0
1
enter the values for adjacency matrix row:8
0
0
0
0
0
0
0
0
Strongly Connected Components:
0
4
1
Strongly Connected Components:
2
3
Strongly Connected Components:
6
5
Strongly Connected Components:
7

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

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.