# Check if graph is strongly connected or not

Graphs are strongly connected, if when every node of path is capable to visit all other node of graph. for example source node V is visit all nodes of graph and others nodes is capable to reach the node V.

In given above graph is strongly connected. because each node are direct and indirect connecting to each other. For example

``````Node 0:
0 -> 4
0 -> 4 -> 3
0 -> 4 -> 3 -> 1
0 -> 4 -> 3 -> 5
or
0 -> 4 -> 3 -> 1 -> 5
//Similar way other nodes
``````

If in this graph are remove edge from (1->0) then graph are not strongly connected because other nodes are not capable to visiting a node (0). for example.

``````Node 0:
0 -> 4
0 -> 4 -> 3
0 -> 4 -> 3 -> 1
0 -> 4 -> 3 -> 5
or
0 -> 4 -> 3 -> 1 -> 5

Node 1:
1 -> 2
1 -> 2 -> 4
1 -> 2 -> 4 -> 3
//not reached to node 0
//so this is not strongly connected
``````

Here given code implementation process.

``````//C Program
//Check if graph is strongly connected or not
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Graph
{
int data; //node key value
struct AjlistNode*next;
};

int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
if(node!=NULL && size>0)
{
int index=0;
for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}else{
printf("Vertic Node is Empty");
}
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E){
//add edge form V to E
//V and E is Node location
if(V<size && E <size){
struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
sizeof(struct AjlistNode)
);
if(newEdge!=NULL){

newEdge->next=NULL;
newEdge->vId=E;

struct AjlistNode *temp=node[V].next;

if(temp==NULL){
node[V].next=newEdge;
}else{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");
}
}else{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V,E);
}
}
void printGraph(struct Graph*node)
{
if(node!=NULL)
{
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
printf("\n Adjacency list of vertex %d  :",index);
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d",node[temp->vId].data);
temp=temp->next;
}
}
}else
{
printf("Empty Graph");
}
}

//pick a path
void DFS(int start,int *visit,struct Graph*node)
{

if(start >size ||start<0 || node==NULL)
{
//invalid input
return ;
}
if(visit[start]==1)
{
return;
}
visit[start]=1;
struct AjlistNode *temp=node[start].next;
while(temp!=NULL)
{
DFS(temp->vId,visit,node);
temp=temp->next;
}
}
//Check path between two nodes
void check_path(int start,
int end,
int *visit,
struct Graph*node,
int *result)
{

if(start >size
|| end >size
|| start<0
|| end<0
|| node==NULL)
{
//invalid input
return ;
}
if(start==end)
{
//when node is connected
visit[start]=1;
*result=1;
return;
}
if(visit[start]==1)
{
return;
}
if(*result==0)
{

visit[start]=1;
struct AjlistNode *temp=node[start].next;
while(temp!=NULL)
{
check_path(temp->vId,end,visit,node,result);
temp=temp->next;
}
}

}

//Handling the execution of two nodes,
//And checking that two nodes are connected or not
void connection(struct Graph*node)
{

int result=1,status=1;

int *visit=(int*)calloc(size,sizeof(int));
//first we are check, node 0 are connected or not to all other nodes
DFS(0,visit,node);

for (int i = 0; i < size; ++i)
{
if(visit[i]!=1)
{
//When not connect
result=0;

break;
}
}

status=result;
//remove memory
free(visit);

visit=NULL;

if(status==1)
{
//Check other nodes are capable to visit first node or not
for (int i = 1; i < size && status==1; ++i)
{
result=0;
//Create memory of visiting nodes
visit=(int*)calloc(size,sizeof(int));

//0 is first node i is other node
check_path(i,0,visit,node,&result);

//remove memory
free(visit);

visit=NULL;
//get new modification
status=result;
}
}

if(status==1)
{
printf("\n Strongly Connected Graph\n");
}else
{
printf("\n Not Strongly Connected Graph\n");
}
}

int main()
{

size=5;
struct Graph*node=NULL;

node=(struct Graph*)malloc(sizeof(struct Graph)*size);

if(node==NULL)
{
printf("\n Memory overflow");
}else
{
//First set node keys
setData(node);

//Connected two node with Edges
printGraph(node);
connection(node);
}
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0  :  4
Adjacency list of vertex 1  :  0  2
Adjacency list of vertex 2  :  1  4
Adjacency list of vertex 3  :  1  2
Adjacency list of vertex 4  :  3
Strongly Connected Graph``````
``````//C++ program
//Check if graph is strongly connected or not
#include<iostream>
using namespace std;

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Vertices
{
int data; //node key value
struct AjlistNode*next;
};

class Graph
{
Vertices *node;
int size;//number of
public:
Graph(int);
void setData();
void printGraph();
void DFS(int ,int *);
void check_path(int ,int ,int *,int *);
void connection();
void connect(int  ,int );
};
Graph::Graph(int size)
{
this->size = size;
//set number of nodes
node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
if(node!=NULL)
{
int index=0;

for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}
else
{
cout<<"Vertic Node is Empty"<<endl;
}
}
//Add Edge from Two given Nodes
void Graph ::connect(int start ,int end)
{
//add edge form start to end
//start and end is Node location
AjlistNode *newEdge=new AjlistNode;

if(newEdge!=NULL)
{

newEdge->next = NULL;
newEdge->vId = end;

AjlistNode *temp=node[start].next;

if(temp==NULL)
{
node[start].next=newEdge;
}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}

}

void Graph ::  addEdge(int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
connect(V,E);

}else
{
//not valid Vertices
cout<<"Invalid Node Vertices "<< V<<" "<<E;
}
}

void Graph::printGraph()
{
if(node!=NULL)
{
AjlistNode *temp=NULL;
for(int index=0; index < size; index++)
{
cout<<"\n Adjacency list of vertex "<<index<<" :";
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

cout<<" "<<node[temp->vId].data;
temp=temp->next;
}
}
}else
{
cout<<"Empty Graph"<<endl;
}
}

//pick a path
void Graph :: DFS(int start,int *visit)
{

if(start >size ||start<0 || node==NULL)
{
//invalid input
return ;
}
if(visit[start]==1)
{
return;
}
visit[start]=1;
struct AjlistNode *temp=node[start].next;
while(temp!=NULL)
{
DFS(temp->vId,visit);
temp=temp->next;
}
}
//Check path between two nodes
void Graph :: check_path(int start,
int end,
int *visit,
int *result)
{

if(start >size
|| end >size
|| start<0
|| end<0
|| node==NULL)
{
//invalid input
return ;
}
if(start==end)
{
//when node is connected
visit[start]=1;
*result=1;
return;
}
if(visit[start]==1)
{
return;
}
if(*result==0)
{

visit[start]=1;
struct AjlistNode *temp=node[start].next;
while(temp!=NULL)
{
check_path(temp->vId,end,visit,result);
temp=temp->next;
}
}

}

//Handling the execution of two nodes,
//And checking that two nodes are connected or not
void Graph :: connection()
{

int result=1,status=1;

int *visit=new int[size];
//first we are check, node 0 are connected or not to all other nodes
DFS(0,visit);

for (int i = 0; i < size; ++i)
{
if(visit[i]!=1)
{
//When not connect
result=0;

break;
}
}

status=result;

if(status==1)
{
//Check other nodes are capable to visit first node or not
for (int i = 1; i < size && status==1; ++i)
{
result=0;
for (int j = 0; j < size; ++j)
{
visit[j]=0;
}

//0 is first node i is other node
check_path(i,0,visit,&result);

//get new modification
status=result;
}
}

if(status==1)
{
cout<<("\n Strongly Connected Graph\n");
}else
{
cout<<("\n Not Strongly Connected Graph\n");
}
}
int main()
{
//Create Object
Graph g=Graph(5);
//First set node keys
g.setData();

//Connected two node with Edges
g.printGraph();
g.connection();
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
``````
``````//Java program
//Check if graph is strongly connected or not
public class MyGraph
{

static class AjlistNode
{
int id;//Vertices node key
AjlistNode next;
}
static class Vertices
{
int data;
AjlistNode next;
}

//number of Vertices
static int size;
int result;
Vertices node[];

MyGraph(int size)
{
//set value
this.size = size;
node = new Vertices[size];
result=0;
}

//set initial node value
public void setData()
{
if(node == null)
{
System.out.println("\nEmpty Graph");

}else
{
for(int index = 0; index < size; index++)
{

node[index]=new Vertices();
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
{
if(start < size && end < size && node != null)
{
connect(start,end);

}else
{
System.out.println("\nInvalid nodes "+start+" "+end);
}
}

public void printGraph()
{

if(size>0 && node!=null)
{
for(int index=0;index<size;index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");

AjlistNode temp=node[index].next;

while(temp!=null)
{
System.out.print(" "+node[temp.id].data);

temp=temp.next;
}
}
}
}

//pick a path
void  DFS(int start,int []visit)
{

if(start >size ||start<0 || this.node==null)
{
//invalid input
return ;
}
if(visit[start]==1)
{
return;
}

visit[start]=1;

AjlistNode  temp=node[start].next;
while(temp!=null)
{
DFS(temp.id,visit);
temp=temp.next;
}
}
//Check path between two nodes
public void  check_path(int start,
int end,
int  []visit)
{

if(start >size
|| end >size
|| start<0
|| end<0
|| this.node==null)
{
//invalid input
return ;
}
if(start == end)
{
//when node is connected
visit[start]=1;
this.result=1;
return;
}
if(visit[start]==1)
{
return;
}
if( this.result==0)
{

visit[start]=1;
AjlistNode  temp=node[start].next;
while(temp!=null)
{
check_path(temp.id,end,visit);
temp=temp.next;
}
}

}

//Handling the execution of two nodes,
//And checking that two nodes are connected or not
public void connection()
{

int status=1;
this.result=1;
int  []visit=new int[size];
//first we are check, node 0 are connected or not to all other nodes
DFS(0,visit);

for (int i = 0; i < size; ++i)
{
if(visit[i]!=1)
{
//When not connect
this.result=0;

break;
}
}

status=this.result;

if(status==1)
{
//Check other nodes are capable to visit first node or not
for (int i = 1; i < size && status==1; ++i)
{
this.result=0;

for (int j = 0; j < size; ++j)
{
visit[j]=0;
}

//0 is first node i is other node
check_path(i,0,visit);

//get new modification
status=result;
}
}

if(status==1)
{
System.out.println("\n Strongly Connected Graph");
}else
{
System.out.println("\n Not Strongly Connected Graph");
}
}

public static void main(String[] args)
{
int totalNode=5;

MyGraph g=new MyGraph(totalNode);

g.setData();

//Connected two node with Edges
g.printGraph();
g.connection();
}
}``````

#### Output

``````Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
``````
``````#Python program
#Check if graph is strongly connected or not

def __init__(self,data):
self.id=data
self.next=None

class Vertices:
def __init__(self,data):
self.data=data
self.next=None

class Graph:
"""Constructor for Graph"""
def __init__(self, size):
self.size=size
self.node=[]
self.result=0

def setData(self):
if(self.size>0 and self.node!=None):
index=0
while(index<self.size):
self.node.append(Vertices(index))
index+=1

#connect two node with  edge
def connect(self,start,end):
if(self.node[start].next==None):
self.node[start].next=new_edge
else:
temp=self.node[start].next
while(temp.next!=None):
temp=temp.next
temp.next=new_edge

#start,end is two nodes
if(self.size>start and self.size>start):

self.connect(start,end)

else:
print("Invalid nodes")

def printGraph(self):

if(self.size>0 and self.node!=None):

index=0

while(index<self.size):

print("\nAdjacency list of vertex  : {0}".format(index),end=" ")

temp=self.node[index].next

while temp!=None:

print(" {0}".format(temp.id),end=" ")

temp=temp.next

index+=1

#pick a path
def  DFS(self,start,visit) :

if(start >self.size or start<0 or  self.node==None) :
#invalid input
return

if(visit[start]==1) :
return

visit[start]=1

temp=self.node[start].next

while(temp!=None):

self.DFS(temp.id,visit)

temp=temp.next

#Check path between two nodes
def  check_path(self, start,end,visit):

if(start > self.size or  end > self.size or  start < 0 or  end < 0 or  self.node==None):
#invalid input
return

if(start == end):
#when node is connected
visit[start]=1
self.result=1
return

if(visit[start]==1):
return

if( self.result==0):

visit[start]=1
temp=self.node[start].next
while(temp!=None):
self.check_path(temp.id,end,visit)
temp=temp.next

#Handling the execution of two nodes,
#And checking that two nodes are connected or not
def connection(self):

status=1
self.result=1
visit=[0]*self.size
#first we are check, node 0 are connected or not to all other nodes
self.DFS(0,visit)
i = 0
while(i<self.size) :

if(visit[i]!=1):
#When not connect
self.result=0
break

i+=1

status=self.result

if(status==1):
i=0

#Check other nodes are capable to visit first node or not
while(i<self.size and status==1) :

self.result=0

visit=[0]*self.size

#0 is first node i is other node
self.check_path(i,0,visit)

i+=1

#get new modification
status=self.result

if(status==1) :
print("\n Strongly Connected Graph")
else :
print("\n Not Strongly Connected Graph")

def main():
g=Graph(5)
g.setData()
#Connected two node with Edges

g.printGraph()
g.connection()

if __name__=="__main__":
main()``````

#### Output

``````Adjacency list of vertex  : 0  4
Adjacency list of vertex  : 1  0  2
Adjacency list of vertex  : 2  1  4
Adjacency list of vertex  : 3  1  2
Adjacency list of vertex  : 4  3
Strongly Connected Graph
``````
``````//C# Graph
//Check if graph is strongly connected or not
using System;

public class AjlistNode
{
public int id;//Vertices node key
public AjlistNode next;
}
public class Vertices
{
public int data;
public AjlistNode next;
}
public class MyGraph
{

//number of Vertices
public int size;
public int result;
public Vertices []node;

public MyGraph(int size)
{
//set value
this.size = size;
node = new Vertices[size];
result=0;
}

//set initial node value
public void setData()
{
if(node == null)
{
Console.WriteLine("\nEmpty Graph");

}else
{
for(int index = 0; index < size; index++)
{

node[index]=new Vertices();
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
{
if(start < size && end < size && node != null)
{
connect(start,end);

}else
{
Console.WriteLine("\nInvalid nodes "+start+" "+end);
}
}

public void printGraph()
{

if(size>0 && node!=null)
{
for(int index=0;index<size;index++)
{
Console.Write("\nAdjacency list of vertex "+index+" :");

AjlistNode temp=node[index].next;

while(temp!=null)
{
Console.Write(" "+node[temp.id].data);

temp=temp.next;
}
}
}
}

//pick a path
void  DFS(int start,int []visit)
{

if(start >size ||start<0 || this.node==null)
{
//invalid input
return ;
}
if(visit[start]==1)
{
return;
}

visit[start]=1;

AjlistNode  temp=node[start].next;
while(temp!=null)
{
DFS(temp.id,visit);
temp=temp.next;
}
}
//Check path between two nodes
public void  check_path(int start,
int end,
int  []visit)
{

if(start >size
|| end >size
|| start<0
|| end<0
|| this.node==null)
{
//invalid input
return ;
}
if(start == end)
{
//when node is connected
visit[start]=1;
this.result=1;
return;
}
if(visit[start]==1)
{
return;
}
if( this.result==0)
{

visit[start]=1;
AjlistNode  temp=node[start].next;
while(temp!=null)
{
check_path(temp.id,end,visit);
temp=temp.next;
}
}

}

//Handling the execution of two nodes,
//And checking that two nodes are connected or not
public void connection()
{

int status=1;
this.result=1;
int  []visit=new int[size];
//first we are check, node 0 are connected or not to all other nodes
DFS(0,visit);

for (int i = 0; i < size; ++i)
{
if(visit[i]!=1)
{
//When not connect
this.result=0;

break;
}
}

status=this.result;

if(status==1)
{
//Check other nodes are capable to visit first node or not
for (int i = 1; i < size && status==1; ++i)
{
this.result=0;

for (int j = 0; j < size; ++j)
{
visit[j]=0;
}

//0 is first node i is other node
check_path(i,0,visit);

//get new modification
status=result;
}
}

if(status==1)
{
Console.WriteLine("\n Strongly Connected Graph");
}else
{
Console.WriteLine("\n Not Strongly Connected Graph");
}
}
}
class Program
{

static void Main(string[] args)
{
int totalNode=5;

MyGraph g=new MyGraph(totalNode);

g.setData();

//Connected two node with Edges
g.printGraph();
g.connection();

}
}``````

#### Output

``````Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
``````
``````<?php
class AjlistNode {
public \$id;
public \$next;
}
class Vertices {
public \$data;
public \$next;
}
class MyGraph {
public \$size;
public \$result;
public \$node;

function __construct(\$size) {
\$this->size = \$size;
\$this->node = [];
\$this->result = 0;
}
public  function setData() {
if (\$this->size <=0 ) {
echo("\nEmpty Graph");
} else {
for (\$index = 0; \$index < \$this->size; \$index++) {
\$this->node[\$index] = new Vertices();
\$this->node[\$index]->data = \$index;
\$this->node[\$index]->next = null;
}
}
}
public  function connect(\$start, \$end) {
\$newEdge = new AjlistNode();
\$newEdge->id = \$end;
\$newEdge->next = null;
if (\$this->node[\$start]->next == null) {
\$this->node[\$start]->next = \$newEdge;
} else {
\$temp = \$this->node[\$start]->next;
while (\$temp->next != null) {
\$temp = \$temp->next;
}
\$temp->next = \$newEdge;
}
}
if (\$start < \$this->size && \$end < \$this->size && \$this->node != null) {
\$this->connect(\$start, \$end);
} else {
echo("\nInvalid nodes ". \$start ." ". \$end);
}
}
public  function printGraph() {
if (\$this->size > 0 && \$this->node != null) {
for (\$index = 0; \$index < \$this->size; \$index++) {
echo("\nAdjacency list of vertex ". \$index ." :");
\$temp = \$this->node[\$index]->next;
while (\$temp != null) {
echo(" ". \$this->node[\$temp->id]->data);
\$temp = \$temp->next;
}
}
}
}

function DFS(\$start, &\$visit) {
if (\$start > \$this->size || \$start < 0 || \$this->node == null) {
return;
}
if (\$visit[\$start] == 1) {
return;
}
\$visit[\$start] = 1;
\$temp = \$this->node[\$start]->next;
while (\$temp != null) {
\$this->DFS(\$temp->id, \$visit);
\$temp = \$temp->next;
}
}
public  function check_path(\$start, \$end, &\$visit) {
if (\$start > \$this->size || \$end > \$this->size || \$start < 0 || \$end < 0 || \$this->node == null) {
return;
}
if (\$start == \$end) {
\$visit[\$start] = 1;
\$this->result = 1;
return;
}
if (\$visit[\$start] == 1) {
return;
}
if (\$this->result == 0) {
\$visit[\$start] = 1;
\$temp = \$this->node[\$start]->next;
while (\$temp != null) {
\$this->check_path(\$temp->id, \$end, \$visit);
\$temp = \$temp->next;
}
}
}
public  function connection() {
\$status = 1;
\$this->result = 1;
\$visit = array_fill(0, \$this->size, 0);
\$this->DFS(0, \$visit);
for (\$i = 0; \$i < \$this->size; ++\$i) {
if (\$visit[\$i] != 1) {
\$this->result = 0;
break;;
}
}
\$status = \$this->result;
if (\$status == 1) {
for (\$i = 1; \$i < \$this->size && \$status == 1; ++\$i) {
\$this->result = 0;
for (\$j = 0; \$j < \$this->size; ++\$j) {
\$visit[\$j] = 0;
}
\$this->check_path(\$i, 0, \$visit);
\$status = \$this->result;
}
}
if (\$status == 1) {
echo("\n Strongly Connected Graph");
} else {
echo("\n Not Strongly Connected Graph");
}
}

}
function main() {
\$totalNode = 5;
\$g = new MyGraph(\$totalNode);
\$g->setData();
\$g->printGraph();
\$g->connection();
}
main();``````

#### Output

``````Adjacency list of vertex 0 : 4
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 : 1 4
Adjacency list of vertex 3 : 1 2
Adjacency list of vertex 4 : 3
Strongly Connected Graph
``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.