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.

```
/*
```

 * C++ Program to Find Strongly Connected Components in Graphs

```
 */
```
```
#include<iostream>
```
```
#include<conio.h>
```
```
using namespace std;
```
```
struct node_info
```
```
{
```
```
    int no;
```
```
    int lv_time, st_time;
```
```
}*q = NULL;
```
```
struct node
```
```
{
```
```
    node_info *pt;
```
```
    node *next;
```
```
}*top = NULL, *p = NULL, *np = NULL;
```
```
struct node1
```
```
{
```
```
    node1 *link;
```
```
    node_info *pt1;
```

}*head = NULL, *m = NULL, *n = NULL, *np1 = NULL;

```
int c = 0;
```
```
void push(node_info *ptr)
```
```
{
```
```
    np = new node;
```
```
    np->pt = ptr;
```
```
    np->next = NULL;
```
```
    if (top == NULL)
```
```
    {
```
```
        top = np;
```
```
    }
```
```
    else
```
```
    {
```
```
        np->next = top;
```
```
        top = np;
```
```
    }
```
```
}
```
```
node_info *pop()
```
```
{
```
```
    if (top == NULL)
```
```
    {
```
```
        cout<<"underflow\n";
```
```
    }
```
```
    else
```
```
    {
```
```
        p = top;
```
```
        top = top->next;
```
```
        return(p->pt);
```
```
        delete(p);
```
```
    }
```
```
}
```
```
void store(node_info *ptr1)
```
```
{
```
```
    np1 = new node1;
```
```
    np1->pt1 = ptr1;
```
```
    np1->link = NULL;
```
```
    if (c == 0)
```
```
    {
```
```
        head = np1;
```
```
        m = head;
```
```
        m->link = NULL;
```
```
        c++;
```
```
    }
```
```
    else
```
```
    {
```
```
        m = head;
```
```
        np1->link = m;
```
```
        head = np1;
```
```
    }
```
```
}
```
```
void remove(int x)
```
```
{
```
```
    m = head;
```
```
    if ((m->pt1)->no == x)
```
```
    {
```
```
        head = head->link;
```
```
        delete(m);
```
```
    }
```
```
    else
```
```
    {
```

        while ((m->pt1)->no != x && m->link != NULL)

```
        {
```
```
            n = m;
```
```
            m = m->link;
```
```
        }
```
```
        if ((m->pt1)->no == x)
```
```
        {
```
```
            n->link = m->link;
```
```
            delete(m);
```
```
        }
```
```
        else if (m->link == NULL)
```
```
        {
```
```
            cout<<"error\n";
```
```
        }
```
```
    }
```
```
}            
```
```
void topo(int *v, int am[][8], int i)
```
```
{
```
```
    q = new node_info;
```
```
    q->no = i;
```
```
    q->st_time = c;
```
```
     push(q);
```
```
    v[i] = 1;
```
```
    for (int j = 0; j < 8; j++)
```
```
    {
```

        if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))

```
            continue;
```

        else if (am[i][j] == 1 && v[j] == 0)

```
        {
```
```
            c++;
```
```
            topo(v,am,j);
```
```
        }
```
```
    }
```
```
    c++;
```
```
    q = pop();
```
```
    q->lv_time = c;
```
```
    store(q);
```
```
    return;
```
```
}
```
```
void topo1(int *v, int am[][8], int i)
```
```
{
```
```
    v[i] = 1;
```
```
    remove(i);
```
```
    cout<<i<<endl;
```
```
    for (int j = 0; j < 8; j++)
```
```
    {
```

        if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))

```
        {
```
```
            continue;
```
```
        }
```

        else if (am[i][j] == 1 && v[j] == 0)

```
        {
```
```
            topo1(v,am,j);
```
```
        }
```
```
    }
```
```
    return;
```
```
}
```
```
int main()
```
```
{
```
```
    int v[8], am[8][8], amt[8][8];
```
```
    for (int i = 0; i < 8; i++)
```
```
        v[i] = 0;
```
```
    for (int i = 0; i < 8; i++)
```
```
    {
```

        cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;

```
        for (int j = 0; j < 8; j++)
```
```
        {
```
```
            cin>>am[i][j];
```
```
        }
```
```
    }
```
```
    topo(v, am, 0);
```
```
    for (int i = 0; i < 8; i++)
```
```
    {
```
```
        v[i] = 0;
```
```
        for (int j = 0; j < 8; j++)
```
```
            amt[j][i] = am[i][j];
```
```
    }
```
```
    while (head != NULL)
```
```
    {
```

        cout<<"Strongly Connected Components:\n";

            topo1(v, amt, (head->pt1)->no);

```
    }
```
```
    getch();
```
```
}
```

 
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.

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

« Prev - C++ Program to Find Number of Cycles in a Graph

» Next - C++ Program to Find All Forward Edges in a Graph

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Programming MCQs
Practice Computer Science MCQs
Check Data Structure Books

Recommended Articles: