# Strongly connected components

In graph theory, a strongly connected component (SCC) of a directed graph is a subset of the vertices such that for any two vertices u and v in the subset, there is a directed path from u to v and a directed path from v to u. In other words, every vertex in the SCC is reachable from every other vertex in the SCC.

Formally, let G = (V, E) be a directed graph. A strongly connected component of G is a maximal subset C of V such that for every pair of vertices u and v in C, there is a directed path from u to v and a directed path from v to u. This means that C is a strongly connected component if and only if it is not contained in any larger strongly connected component.

The concept of strongly connected components is useful in many areas of computer science and mathematics, such as in algorithms for finding cycles in directed graphs, in the analysis of networks and circuits, and in the study of automata and formal languages. There are efficient algorithms for finding all the strongly connected components of a directed graph, such as Kosaraju's algorithm and Tarjan's algorithm.

## Program Solution

``````import java.util.Stack;
/*
Java Program
Strongly connected components
*/
// Define edge of graph node
class AjlistNode
{
//Vertices id
public int id;
public AjlistNode next;
public AjlistNode(int id)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
class GraphNode
{
//node key value
public int data;
public AjlistNode edge;
public GraphNode(int data)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
public class MyGraph
{
// Number of graph nodes
public int size;
public GraphNode[] node;
public MyGraph(int size)
{
if (size < 0)
{
System.out.print("\n Invalid size of nodes " + size + " \n");
}
else
{
this.size = size;
this.node = new GraphNode[this.size];
int i = 0;
// Set graph node level and e
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphNode(i);
}
}
}
//This function are connect nodes with one edge
public void connectEdge(int a, int b)
{
if (this.size <= 0)
{
System.out.print("\n Graph have no nodes \n");
return;
}
AjlistNode newEdge = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
AjlistNode edge = this.node[a].edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
System.out.print("\n Memory overflow,");
System.out.print(" When connect a new edge from");
System.out.print(" (" + a + " to " + b + " ) nodes. \n");
}
}
// This function is add new edge
public void addEdge(int a, int b)
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
connectEdge(a, b);
}
else
{
//not valid Vertices
System.out.print("Invalid Node Vertices " + a + " " + b);
}
}
public void printGraph()
{
if (this.size > 0)
{
AjlistNode temp = null;
// Loop controlling variable
int i = 0;
for (i = 0; i < this.size; i++)
{
System.out.print("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i].edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
System.out.print("  " + this.node[temp.id].data);
temp = temp.next;
}
}
}
else
{
System.out.print("Empty Graph Node");
}
}
// Set the default value in visited node
public void resetDefault(boolean[] visit, int n)
{
for (int i = 0; i < n; ++i)
{
visit[i] = false;
}
}
//  Find order of path in given current node
public void fillOrder(int current,
boolean visit[], Stack < Integer > record)
{
if (visit[current] == true)
{
return;
}
AjlistNode temp = this.node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
fillOrder(temp.id, visit, record);
// Visit to next edge
temp = temp.next;
}
// Add the visited current node
record.push(current);
}
// Display graph nodes using DFS
public void printPath(int current, boolean visit[])
{
if (visit[current] == true)
{
return;
}
System.out.print(" " + current);
AjlistNode temp = this.node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
printPath(temp.id, visit);
// Visit to next edge
temp = temp.next;
}
}
// This function are add new edge
public void transposeEdge(AjlistNode e, int point)
{
AjlistNode current = null;
while (e != null)
{
current = e;
// visit to next edge
e = e.next;
// Make sure given node is is valid
if (current.id < this.size)
{
current.next = node[current.id].edge;
//set node key value
node[current.id].edge = current;
current.id = point;
}
}
}
// This function are remove node edges
public void transpose(int point)
{
if (point < this.size)
{
AjlistNode e = this.node[point].edge;
// Segregating the edge
this.node[point].edge = null;
// Recursively call to next node
transpose(point + 1);
// This method are combine new edges
transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
public void scc()
{
if (this.size > 0)
{
boolean[] visit = new boolean[this.size];
// initial no node visit
resetDefault(visit, this.size);

// Use to collect visited node in reverse order
Stack < Integer > record = new Stack < Integer > ();

// Collect visited node information in record
for (int i = 0; i < this.size; i++)
{
if (visit[i] == false)
{
fillOrder(i, visit, record);
}
}
// Transpose the graph edges
transpose(0);

System.out.print("\n Strongly sonnected components \n");
// initial no node visit
resetDefault(visit, this.size);

// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!record.isEmpty())
{
if (visit[record.peek()] == false)
{
// Dfs traverse
printPath(record.peek(), visit);

System.out.print("\n");
}
record.pop();
}

// Transpose the graph edges and back to original graph
transpose(0);
}
}
public static void main(String[] args)
{
// 9 is number of nodes
MyGraph graph = new MyGraph(9);
// Connected two node with Edges

// Print graph nodes and associative edges
graph.printGraph();
// Print all strongly connected components
graph.scc();

}
}``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````
``````// Include header file
#include <iostream>

#include <stack>

using namespace std;
/*
C++ Program
Strongly connected components
*/
// Define edge of graph node
class AjlistNode
{
public:
// Vertices id
int id;
AjlistNode *next;
AjlistNode(int id)
{
this->id = id;
this->next = NULL;
}
};
// Define node of graph
class GraphNode
{
public:
// node key value
int data;
AjlistNode *edge;
GraphNode()
{
this->data = 0;
this->edge = NULL;
}
GraphNode(int data)
{
this->data = data;
this->edge = NULL;
}
};
// Define structure of graph
class MyGraph
{
public:
// Number of graph nodes
int size;
GraphNode *node;
MyGraph(int size)
{
if (size < 0)
{
cout << "\n Invalid size of nodes " << size << " \n";
}
else
{
this->size = size;
this->node = new GraphNode[this->size];
int i = 0;
//   Set graph node level and e
i = 0;
while (i < this->size)
{
this->node[i].data = i;
this->node[i].edge = NULL;
i++;
}
}
}
//This function are connect nodes with one edge
void connectEdge(int a, int b)
{
if (this->size <= 0)
{
cout << "\n Graph have no nodes \n";
return;
}
AjlistNode *newEdge = new AjlistNode(b);
if (newEdge != NULL)
{
// Get first edge of [i] node
AjlistNode *edge = this->node[a].edge;
if (edge == NULL)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this->node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge->next != NULL)
{
edge = edge->next;
}
// Add edge at last position
edge->next = newEdge;
}
}
else
{
cout << "\n Memory overflow,";
cout << " When connect a new edge from";
cout << " (" << a << " to " << b << " ) nodes. \n";
}
}
// This function is add new edge
{
if (this->size > 0 && a < this->size && b < this->size)
{
// connect edge
// a---->b
this->connectEdge(a, b);
}
else
{
//not valid Vertices
cout << "Invalid Node Vertices " << a << " " << b;
}
}
void printGraph()
{
if (this->size > 0)
{
AjlistNode *temp = NULL;
// Loop controlling variable
int i = 0;
for (i = 0; i < this->size; i++)
{
cout << "\n Adjacency list of vertex " << i << " :";
// Get first edge of [i] node
temp = this->node[i].edge;
while (temp != NULL)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
cout << "  " << this->node[temp->id].data;
temp = temp->next;
}
}
}
else
{
cout << "Empty Graph Node";
}
}
// Set the default value in visited node
void resetDefault(bool visit[], int n)
{
for (int i = 0; i < n; ++i)
{
visit[i] = false;
}
}
//  Find order of path in given current node
void fillOrder(int current, bool visit[], stack < int > &record)
{
if (visit[current] == true)
{
return;
}
AjlistNode *temp = this->node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != NULL)
{
this->fillOrder(temp->id, visit, record);
// Visit to next edge
temp = temp->next;
}
// Add the visited current node
record.push(current);
}
// Display graph nodes using DFS
void printPath(int current, bool visit[])
{
if (visit[current] == true)
{
return;
}
cout << " " << current;
AjlistNode *temp = this->node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != NULL)
{
this->printPath(temp->id, visit);
// Visit to next edge
temp = temp->next;
}
}
// This function are add new edge
void transposeEdge(AjlistNode *e, int point)
{
AjlistNode *current = NULL;
while (e != NULL)
{
current = e;
// visit to next edge
e = e->next;
// Make sure given node is is valid
if (current->id < this->size)
{
current->next = this->node[current->id].edge;
//set node key value
this->node[current->id].edge = current;
current->id = point;
}
}
}
// This function are remove node edges
void transpose(int point)
{
if (point < this->size)
{
AjlistNode *e = this->node[point].edge;
// Segregating the edge
this->node[point].edge = NULL;
// Recursively call to next node
this->transpose(point + 1);
// This method are combine new edges
this->transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
void scc()
{
if (this->size > 0)
{
bool *visit = new bool[this->size];
// initial no node visit
this->resetDefault(visit, this->size);
// Use to collect visited node in reverse order
stack < int > record ;
// Collect visited node information in record
for (int i = 0; i < this->size; i++)
{
if (visit[i] == false)
{
this->fillOrder(i, visit, record);
}
}
// Transpose the graph edges
this->transpose(0);
cout << "\n Strongly sonnected components \n";
// initial no node visit
this->resetDefault(visit, this->size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!record.empty())
{
if (visit[record.top()] == false)
{
// Dfs traverse
this->printPath(record.top(), visit);
cout << "\n";
}
record.pop();
}
// Transpose the graph edges and back to original graph
this->transpose(0);
}
}
};
int main()
{
// 9 is number of nodes
MyGraph *graph = new MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
graph->printGraph();
// Print all strongly connected components
graph->scc();
return 0;
}``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Strongly connected components
*/
// Define edge of graph node
public class AjlistNode
{
// Vertices id
public int id;
public AjlistNode next;
public AjlistNode(int id)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
public class GraphNode
{
// node key value
public int data;
public AjlistNode edge;
public GraphNode(int data)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
public class MyGraph
{
// Number of graph nodes
public int size;
public GraphNode[] node;
public MyGraph(int size)
{
if (size < 0)
{
Console.Write("\n Invalid size of nodes " + size + " \n");
}
else
{
this.size = size;
this.node = new GraphNode[this.size];
int i = 0;
// Set graph node level and e
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphNode(i);
}
}
}
//This function are connect nodes with one edge
public void connectEdge(int a, int b)
{
if (this.size <= 0)
{
Console.Write("\n Graph have no nodes \n");
return;
}
AjlistNode newEdge = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
AjlistNode edge = this.node[a].edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
Console.Write("\n Memory overflow,");
Console.Write(" When connect a new edge from");
Console.Write(" (" + a + " to " + b + " ) nodes. \n");
}
}
// This function is add new edge
public void addEdge(int a, int b)
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
this.connectEdge(a, b);
}
else
{
//not valid Vertices
Console.Write("Invalid Node Vertices " + a + " " + b);
}
}
public void printGraph()
{
if (this.size > 0)
{
AjlistNode temp = null;
// Loop controlling variable
int i = 0;
for (i = 0; i < this.size; i++)
{
Console.Write("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i].edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
Console.Write("  " + this.node[temp.id].data);
temp = temp.next;
}
}
}
else
{
Console.Write("Empty Graph Node");
}
}
// Set the default value in visited node
public void resetDefault(Boolean[] visit, int n)
{
for (int i = 0; i < n; ++i)
{
visit[i] = false;
}
}
//  Find order of path in given current node
public void fillOrder(int current, Boolean[] visit, Stack < int > record)
{
if (visit[current] == true)
{
return;
}
AjlistNode temp = this.node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
this.fillOrder(temp.id, visit, record);
// Visit to next edge
temp = temp.next;
}
// Add the visited current node
record.Push(current);
}
// Display graph nodes using DFS
public void printPath(int current, Boolean[] visit)
{
if (visit[current] == true)
{
return;
}
Console.Write(" " + current);
AjlistNode temp = this.node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
this.printPath(temp.id, visit);
// Visit to next edge
temp = temp.next;
}
}
// This function are add new edge
public void transposeEdge(AjlistNode e, int point)
{
AjlistNode current = null;
while (e != null)
{
current = e;
// visit to next edge
e = e.next;
// Make sure given node is is valid
if (current.id < this.size)
{
current.next = this.node[current.id].edge;
//set node key value
this.node[current.id].edge = current;
current.id = point;
}
}
}
// This function are remove node edges
public void transpose(int point)
{
if (point < this.size)
{
AjlistNode e = this.node[point].edge;
// Segregating the edge
this.node[point].edge = null;
// Recursively call to next node
this.transpose(point + 1);
// This method are combine new edges
this.transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
public void scc()
{
if (this.size > 0)
{
Boolean[] visit = new Boolean[this.size];
// initial no node visit
this.resetDefault(visit, this.size);
// Use to collect visited node in reverse order
Stack < int > record = new Stack < int > ();
// Collect visited node information in record
for (int i = 0; i < this.size; i++)
{
if (visit[i] == false)
{
this.fillOrder(i, visit, record);
}
}
// Transpose the graph edges
this.transpose(0);
Console.Write("\n Strongly sonnected components \n");
// initial no node visit
this.resetDefault(visit, this.size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!(record.Count == 0))
{
if (visit[record.Peek()] == false)
{
// Dfs traverse
this.printPath(record.Peek(), visit);
Console.Write("\n");
}
record.Pop();
}
// Transpose the graph edges and back to original graph
this.transpose(0);
}
}
public static void Main(String[] args)
{
// 9 is number of nodes
MyGraph graph = new MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
graph.printGraph();
// Print all strongly connected components
graph.scc();
}
}``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````
``````<?php
/*
Php Program
Strongly connected components
*/
// Define edge of graph node
class AjlistNode
{
//Vertices id
public \$id;
public \$next;
public	function __construct(\$id)
{
\$this->id = \$id;
\$this->next = NULL;
}
}
// Define node of graph
class GraphNode
{
//node key value
public \$data;
public \$edge;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->edge = NULL;
}
}
// Define structure of graph
class MyGraph
{
// Number of graph nodes
public \$size;
public \$node;
public	function __construct(\$size)
{
if (\$size < 0)
{
echo("\n Invalid size of nodes ".\$size.
" \n");
}
else
{
\$this->size = \$size;
\$this->node = array_fill(0, \$this->size, NULL);
\$i = 0;
// Set graph node level and e
for (\$i = 0; \$i < \$this->size; \$i++)
{
\$this->node[\$i] = new GraphNode(\$i);
}
}
}
//This function are connect nodes with one edge
public	function connectEdge(\$a, \$b)
{
if (\$this->size <= 0)
{
echo("\n Graph have no nodes \n");
return;
}
\$newEdge = new AjlistNode(\$b);
if (\$newEdge != NULL)
{
// Get first edge of [i] node
\$edge = \$this->node[\$a]->edge;
if (\$edge == NULL)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
\$this->node[\$a]->edge = \$newEdge;
}
else
{
//Find last location to add new edge
while (\$edge->next != NULL)
{
\$edge = \$edge->next;
}
// Add edge at last position
\$edge->next = \$newEdge;
}
}
else
{
echo("\n Memory overflow,");
echo(" When connect a new edge from");
echo(" (".\$a." to ".\$b." ) nodes. \n");
}
}
// This function is add new edge
{
if (\$this->size > 0 && \$a < \$this->size && \$b < \$this->size)
{
// connect edge
// a---->b
\$this->connectEdge(\$a, \$b);
}
else
{
//not valid Vertices
echo("Invalid Node Vertices ".\$a." ".\$b);
}
}
public	function printGraph()
{
if (\$this->size > 0)
{
\$temp = NULL;
// Loop controlling variable
\$i = 0;
for (\$i = 0; \$i < \$this->size; \$i++)
{
echo("\n Adjacency list of vertex ".\$i." :");
// Get first edge of [i] node
\$temp = \$this->node[\$i]->edge;
while (\$temp != NULL)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
echo("  ".\$this->node[\$temp->id]->data);
\$temp = \$temp->next;
}
}
}
else
{
echo("Empty Graph Node");
}
}
// Set the default value in visited node
public	function resetDefault(&\$visit, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
\$visit[\$i] = false;
}
}
//  Find order of path in given current node
public	function fillOrder(\$current, &\$visit, &\$record)
{
if (\$visit[\$current] == true)
{
return;
}
\$temp = \$this->node[\$current]->edge;
// Active the visiting node status
\$visit[\$current] = true;
// iterating the nodes edges
while (\$temp != NULL)
{
\$this->fillOrder(\$temp->id, \$visit, \$record);
// Visit to next edge
\$temp = \$temp->next;
}
// Add the visited current node
array_push(\$record, \$current);
}
// Display graph nodes using DFS
public	function printPath(\$current, &\$visit)
{
if (\$visit[\$current] == true)
{
return;
}
echo(" ".\$current);
\$temp = \$this->node[\$current]->edge;
// Active the visiting node status
\$visit[\$current] = true;
// iterating the nodes edges
while (\$temp != NULL)
{
\$this->printPath(\$temp->id, \$visit);
// Visit to next edge
\$temp = \$temp->next;
}
}
// This function are add new edge
public	function transposeEdge(\$e, \$point)
{
\$current = NULL;
while (\$e != NULL)
{
\$current = \$e;
// visit to next edge
\$e = \$e->next;
// Make sure given node is is valid
if (\$current->id < \$this->size)
{
\$current->next = \$this->node[\$current->id]->edge;
//set node key value
\$this->node[\$current->id]->edge = \$current;
\$current->id = \$point;
}
}
}
// This function are remove node edges
public	function transpose(\$point)
{
if (\$point < \$this->size)
{
\$e = \$this->node[\$point]->edge;
// Segregating the edge
\$this->node[\$point]->edge = NULL;
// Recursively call to next node
\$this->transpose(\$point + 1);
// This method are combine new edges
\$this->transposeEdge(\$e, \$point);
}
}
// Handles the request of find strongly sonnected components
public	function scc()
{
if (\$this->size > 0)
{
\$visit = array_fill(0, \$this->size, false);
// Use to collect visited node in reverse order
\$record = array();
// Collect visited node information in record
for (\$i = 0; \$i < \$this->size; \$i++)
{
if (\$visit[\$i] == false)
{
\$this->fillOrder(\$i, \$visit, \$record);
}
}

// Transpose the graph edges
\$this->transpose(0);
echo("\n Strongly sonnected components \n");
// initial no node visit
\$this->resetDefault(\$visit, \$this->size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (empty(\$record)==false)
{
if (\$visit[end(\$record)] == false)
{
// Dfs traverse
\$this->printPath(end(\$record), \$visit);
echo("\n");
}
array_pop(\$record);
}
// Transpose the graph edges and back to original graph
\$this->transpose(0);
}
}
}

function main()
{
// 9 is number of nodes
\$graph = new MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
\$graph->printGraph();
// Print all strongly connected components
\$graph->scc();
}
main();``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````
``````/*
Node JS Program
Strongly connected components
*/
// Define edge of graph node
class AjlistNode
{
constructor(id)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
class GraphNode
{
constructor(data)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
class MyGraph
{
constructor(size)
{
if (size < 0)
{
process.stdout.write("\n Invalid size of nodes " + size + " \n");
}
else
{
this.size = size;
this.node = Array(this.size).fill(null);
var i = 0;
// Set graph node level and e
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphNode(i);
}
}
}
//This function are connect nodes with one edge
connectEdge(a, b)
{
if (this.size <= 0)
{
process.stdout.write("\n Graph have no nodes \n");
return;
}
var newEdge = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
var edge = this.node[a].edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
process.stdout.write("\n Memory overflow,");
process.stdout.write(" When connect a new edge from");
process.stdout.write(" (" + a + " to " + b + " ) nodes. \n");
}
}
// This function is add new edge
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
this.connectEdge(a, b);
}
else
{
//not valid Vertices
process.stdout.write("Invalid Node Vertices " + a + " " + b);
}
}
printGraph()
{
if (this.size > 0)
{
var temp = null;
// Loop controlling variable
var i = 0;
for (i = 0; i < this.size; i++)
{
process.stdout.write("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i].edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
process.stdout.write("  " + this.node[temp.id].data);
temp = temp.next;
}
}
}
else
{
process.stdout.write("Empty Graph Node");
}
}
// Set the default value in visited node
resetDefault(visit, n)
{
for (var i = 0; i < n; ++i)
{
visit[i] = false;
}
}
//  Find order of path in given current node
fillOrder(current, visit, record)
{
if (visit[current] == true)
{
return;
}
var temp = this.node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
this.fillOrder(temp.id, visit, record);
// Visit to next edge
temp = temp.next;
}
// Add the visited current node
record.push(current);
}
// Display graph nodes using DFS
printPath(current, visit)
{
if (visit[current] == true)
{
return;
}
process.stdout.write(" " + current);
var temp = this.node[current].edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
this.printPath(temp.id, visit);
// Visit to next edge
temp = temp.next;
}
}
// This function are add new edge
transposeEdge(e, point)
{
var current = null;
while (e != null)
{
current = e;
// visit to next edge
e = e.next;
// Make sure given node is is valid
if (current.id < this.size)
{
current.next = this.node[current.id].edge;
//set node key value
this.node[current.id].edge = current;
current.id = point;
}
}
}
// This function are remove node edges
transpose(point)
{
if (point < this.size)
{
var e = this.node[point].edge;
// Segregating the edge
this.node[point].edge = null;
// Recursively call to next node
this.transpose(point + 1);
// This method are combine new edges
this.transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
scc()
{
if (this.size > 0)
{
var visit = Array(this.size).fill(false);

// Use to collect visited node in reverse order
var record = [];
// Collect visited node information in record
for (var i = 0; i < this.size; i++)
{
if (visit[i] == false)
{
this.fillOrder(i, visit, record);
}
}
// Transpose the graph edges
this.transpose(0);
process.stdout.write("\n Strongly sonnected components \n");
// initial no node visit
this.resetDefault(visit, this.size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!(record.length == 0))
{
if (visit[record[record.length - 1]] == false)
{
// Dfs traverse
this.printPath(record[record.length - 1], visit);
process.stdout.write("\n");
}
record.pop();
}
// Transpose the graph edges and back to original graph
this.transpose(0);
}
}
}

function main()
{
// 9 is number of nodes
var graph = new MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
graph.printGraph();
// Print all strongly connected components
graph.scc();
}
main();``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````
``````#  Python 3 Program
#  Strongly connected components

#  Define edge of graph node
class AjlistNode :
# Vertices id
def __init__(self, id) :
self.id = id
self.next = None

#  Define node of graph
class GraphNode :
# node key value
def __init__(self, data) :
self.data = data
self.edge = None

#  Define structure of graph
class MyGraph :
#  Number of graph nodes
def __init__(self, size) :
if (size < 0) :
print("\n Invalid size of nodes ", size ," ")
else :
self.size = size
self.node = [None] * (self.size)
i = 0
#  Set graph node level and e
while (i < self.size) :
self.node[i] = GraphNode(i)
i += 1

# This function are connect nodes with one edge
def connectEdge(self, a, b) :
if (self.size <= 0) :
print("\n Graph have no nodes ")
return

newEdge = AjlistNode(b)
if (newEdge != None) :
#  Get first edge of [i] node
edge = self.node[a].edge
if (edge == None) :
#  Whe no edge of graph node [i] then
#  Add a first edge of a [i] node
self.node[a].edge = newEdge
else :
# Find last location to add new edge
while (edge.next != None) :
edge = edge.next

#  Add edge at last position
edge.next = newEdge

else :
print("\n Memory overflow,", end = "")
print(" When connect a new edge from", end = "")
print(" (", a ," to ", b ," ) nodes. ")

#  This function is add new edge
if (self.size > 0 and a < self.size and b < self.size) :
#  connect edge
#  a---->b
self.connectEdge(a, b)
else :
# not valid Vertices
print("Invalid Node Vertices ", a ," ", b, end = "")

# Display Adjacency list of vertex
def printGraph(self) :
if (self.size > 0) :
temp = None
#  Loop controlling variable
i = 0
while (i < self.size) :
print("\n Adjacency list of vertex ", i ," :", end = "")
#  Get first edge of [i] node
temp = self.node[i].edge
while (temp != None) :
# temp->id is graph node vertices
# in this case temp->id is same as
# node[temp->id].data
print("  ", self.node[temp.id].data, end = "")
temp = temp.next

i += 1

else :
print("Empty Graph Node", end = "")

#  Set the default value in visited node
def resetDefault(self, visit, n) :
i = 0
while (i < n) :
visit[i] = False
i += 1

#   Find order of path in given current node
def fillOrder(self, current, visit, record) :
if (visit[current] == True) :
return

temp = self.node[current].edge
#  Active the visiting node status
visit[current] = True
#  iterating the nodes edges
while (temp != None) :
self.fillOrder(temp.id, visit, record)
#  Visit to next edge
temp = temp.next

#  Add the visited current node
record.append(current)

#  Display graph nodes using DFS
def printPath(self, current, visit) :
if (visit[current] == True) :
return

print(" ", current, end = "")
temp = self.node[current].edge
#  Active the visiting node status
visit[current] = True
#  iterating the nodes edges
while (temp != None) :
self.printPath(temp.id, visit)
#  Visit to next edge
temp = temp.next

#  This function are add new edge
def transposeEdge(self, e, point) :
current = None
while (e != None) :
current = e
#  visit to next edge
e = e.next
#  Make sure given node is is valid
if (current.id < self.size) :
current.next = self.node[current.id].edge
# set node key value
self.node[current.id].edge = current
current.id = point

#  This function are remove node edges
def transpose(self, point) :
if (point < self.size) :
e = self.node[point].edge
#  Segregating the edge
self.node[point].edge = None
#  Recursively call to next node
self.transpose(point + 1)
#  This method are combine new edges
self.transposeEdge(e, point)

#  Handles the request of find strongly sonnected components
def scc(self) :
if (self.size > 0) :
visit = [False] * (self.size)
#  initial no node visit
self.resetDefault(visit, self.size)
#  Use to collect visited node in reverse order
record = []
#  Collect visited node information in record
i = 0
while (i < self.size) :
if (visit[i] == False) :
self.fillOrder(i, visit, record)

i += 1

#  Transpose the graph edges
self.transpose(0)
print("\n Strongly sonnected components ")
#  initial no node visit
self.resetDefault(visit, self.size)
#  Execute loop until when record is not empty
#  Traverse dfs in transpose graph
while (not(len(record) == 0)) :
if (visit[record[-1]] == False) :
#  Dfs traverse
self.printPath(record[-1], visit)
print(end = "\n")

record.pop()

#  Transpose the graph edges and back to original graph
self.transpose(0)

def main() :
#  9 is number of nodes
graph = MyGraph(9)
#  Connected two node with Edges
#  Print graph nodes and associative edges
graph.printGraph()
#  Print all strongly connected components
graph.scc()

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

#### input

`````` Adjacency list of vertex  0  :   1
Adjacency list of vertex  1  :   2   4   5
Adjacency list of vertex  2  :   3   6
Adjacency list of vertex  3  :   2   7
Adjacency list of vertex  4  :   0   5
Adjacency list of vertex  5  :   6   8
Adjacency list of vertex  6  :   5
Adjacency list of vertex  7  :   3   6
Adjacency list of vertex  8  :
Strongly sonnected components
0  4  1
2  3  7
6  5
8``````
``````#  Ruby Program
#  Strongly connected components

#  Define edge of graph node
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_accessor :id, :next
# Vertices id
def initialize(id)
self.id = id
self.next = nil
end

end

#  Define node of graph
class GraphNode
# Define the accessor and reader of class GraphNode
attr_accessor :data, :edge
# node key value
def initialize(data)
self.data = data
self.edge = nil
end

end

#  Define structure of graph
class MyGraph
# Define the accessor and reader of class MyGraph
attr_accessor :size, :node
#  Number of graph nodes
def initialize(size)
if (size < 0)
print("\n Invalid size of nodes ", size ," \n")
else

self.size = size
self.node = Array.new(self.size) {nil}
i = 0
#  Set graph node level and e
i = 0
while (i < self.size)
self.node[i] = GraphNode.new(i)
i += 1
end

end

end

# This function are connect nodes with one edge
def connectEdge(a, b)
if (self.size <= 0)
print("\n Graph have no nodes \n")
return
end

newEdge = AjlistNode.new(b)
if (newEdge != nil)
#  Get first edge of [i] node
edge = self.node[a].edge
if (edge == nil)
#  Whe no edge of graph node [i] then
#  Add a first edge of a [i] node
self.node[a].edge = newEdge
else

# Find last location to add new edge
while (edge.next != nil)
edge = edge.next
end

#  Add edge at last position
edge.next = newEdge
end

else

print("\n Memory overflow,")
print(" When connect a new edge from")
print(" (", a ," to ", b ," ) nodes. \n")
end

end

#  This function is add new edge
if (self.size > 0 && a < self.size && b < self.size)
#  connect edge
#  a---->b
self.connectEdge(a, b)
else

# not valid Vertices
print("Invalid Node Vertices ", a ," ", b)
end

end

# Display Adjacency list of vertex
def printGraph()
if (self.size > 0)
temp = nil
#  Loop controlling variable
i = 0
i = 0
while (i < self.size)
print("\n Adjacency list of vertex ", i ," :")
#  Get first edge of [i] node
temp = self.node[i].edge
while (temp != nil)
# temp->id is graph node vertices
# in this case temp->id is same as
# node[temp->id].data
print("  ", self.node[temp.id].data)
temp = temp.next
end

i += 1
end

else

print("Empty Graph Node")
end

end

#  Set the default value in visited node
def resetDefault(visit, n)
i = 0
while (i < n)
visit[i] = false
i += 1
end

end

#   Find order of path in given current node
def fillOrder(current, visit, record)
if (visit[current] == true)
return
end

temp = self.node[current].edge
#  Active the visiting node status
visit[current] = true
#  iterating the nodes edges
while (temp != nil)
self.fillOrder(temp.id, visit, record)
#  Visit to next edge
temp = temp.next
end

#  Add the visited current node
record.push(current)
end

#  Display graph nodes using DFS
def printPath(current, visit)
if (visit[current] == true)
return
end

print(" ", current)
temp = self.node[current].edge
#  Active the visiting node status
visit[current] = true
#  iterating the nodes edges
while (temp != nil)
self.printPath(temp.id, visit)
#  Visit to next edge
temp = temp.next
end

end

#  This function are add new edge
def transposeEdge(e, point)
current = nil
while (e != nil)
current = e
#  visit to next edge
e = e.next
#  Make sure given node is is valid
if (current.id < self.size)
current.next = self.node[current.id].edge
# set node key value
self.node[current.id].edge = current
current.id = point
end

end

end

#  This function are remove node edges
def transpose(point)
if (point < self.size)
e = self.node[point].edge
#  Segregating the edge
self.node[point].edge = nil
#  Recursively call to next node
self.transpose(point + 1)
#  This method are combine new edges
self.transposeEdge(e, point)
end

end

#  Handles the request of find strongly sonnected components
def scc()
if (self.size > 0)
visit = Array.new(self.size) {false}
#  Use to collect visited node in reverse order
record = []
#  Collect visited node information in record
i = 0
while (i < self.size)
if (visit[i] == false)
self.fillOrder(i, visit, record)
end

i += 1
end

#  Transpose the graph edges
self.transpose(0)
print("\n Strongly sonnected components \n")
#  initial no node visit
self.resetDefault(visit, self.size)
#  Execute loop until when record is not empty
#  Traverse dfs in transpose graph
while (!(record.length == 0))
if (visit[record.last] == false)
#  Dfs traverse
self.printPath(record.last, visit)
print("\n")
end

record.pop()
end

#  Transpose the graph edges and back to original graph
self.transpose(0)
end

end

end

def main()
#  9 is number of nodes
graph = MyGraph.new(9)
#  Connected two node with Edges
#  Print graph nodes and associative edges
graph.printGraph()
#  Print all strongly connected components
graph.scc()
end

main()``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8
``````
``````import scala.collection.mutable._;
/*
Scala Program
Strongly connected components
*/
// Define edge of graph node
class AjlistNode(var id: Int , var next: AjlistNode)
{
def this(id: Int)
{
this(id, null);
}
}
// Define node of graph
class GraphNode(var data: Int , var edge: AjlistNode)
{
def this(data: Int)
{
this(data, null);
}
}
class MyGraph(var size: Int , var node: Array[GraphNode])
{
def this(size: Int)
{
this(size, Array.fill[GraphNode](size)(null));

if (size > 0)
{
var i: Int = 0;
//  Set graph node level and e
while (i < this.size)
{
this.node(i) = new GraphNode(i);
i += 1;
}
}
}
//This function are connect nodes with one edge
def connectEdge(a: Int, b: Int): Unit = {
if (this.size <= 0)
{
print("\n Graph have no nodes \n");
return;
}
var newEdge: AjlistNode = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
var edge: AjlistNode = this.node(a).edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node(a).edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
print("\n Memory overflow,");
print(" When connect a new edge from");
print(" (" + a + " to " + b + " ) nodes. \n");
}
}
// This function is add new edge
def addEdge(a: Int, b: Int): Unit = {
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
connectEdge(a, b);
}
else
{
//not valid Vertices
print("Invalid Node Vertices " + a + " " + b);
}
}
def printGraph(): Unit = {
if (this.size > 0)
{
var temp: AjlistNode = null;
// Loop controlling variable
var i: Int = 0;
i = 0;
while (i < this.size)
{
print("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node(i).edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
print("  " + this.node(temp.id).data);
temp = temp.next;
}
i += 1;
}
}
else
{
print("Empty Graph Node");
}
}
// Set the default value in visited node
def resetDefault(visit: Array[Boolean], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
visit(i) = false;
i += 1;
}
}
//  Find order of path in given current node
def fillOrder(current: Int, visit: Array[Boolean], record: Stack[Int]): Unit = {
if (visit(current) == true)
{
return;
}
var temp: AjlistNode = this.node(current).edge;
// Active the visiting node status
visit(current) = true;
// iterating the nodes edges
while (temp != null)
{
fillOrder(temp.id, visit, record);
// Visit to next edge
temp = temp.next;
}
// Add the visited current node
record.push(current);
}
// Display graph nodes using DFS
def printPath(current: Int, visit: Array[Boolean]): Unit = {
if (visit(current) == true)
{
return;
}
print(" " + current);
var temp: AjlistNode = this.node(current).edge;
// Active the visiting node status
visit(current) = true;
// iterating the nodes edges
while (temp != null)
{
printPath(temp.id, visit);
// Visit to next edge
temp = temp.next;
}
}
// This function are add new edge
def transposeEdge(edges: AjlistNode, point: Int): Unit = {
var current: AjlistNode = null;
var e: AjlistNode = edges;
while (e != null)
{
current = e;
// visit to next edge
e = e.next;
// Make sure given node is is valid
if (current.id < this.size)
{
current.next = node(current.id).edge;
//set node key value
node(current.id).edge = current;
current.id = point;
}
}
}
// This function are remove node edges
def transpose(point: Int): Unit = {
if (point < this.size)
{
var e: AjlistNode = this.node(point).edge;
// Segregating the edge
this.node(point).edge = null;
// Recursively call to next node
transpose(point + 1);
// This method are combine new edges
transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
def scc(): Unit = {
if (this.size > 0)
{
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
// Use to collect visited node in reverse order
var record: Stack[Int] = new Stack[Int]();
// Collect visited node information in record
var i: Int = 0;
while (i < this.size)
{
if (visit(i) == false)
{
fillOrder(i, visit, record);
}
i += 1;
}
// Transpose the graph edges
transpose(0);
print("\n Strongly sonnected components \n");
// initial no node visit
resetDefault(visit, this.size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!record.isEmpty)
{
if (visit(record.top) == false)
{
// Dfs traverse
printPath(record.top, visit);
print("\n");
}
record.pop;
}
// Transpose the graph edges and back to original graph
transpose(0);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// 9 is number of nodes
var graph: MyGraph = new MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
graph.printGraph();
// Print all strongly connected components
graph.scc();
}
}``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````
``````import Foundation;
/*
Swift 4 Program
Strongly connected components
*/
// Implement stack
struct Stack
{
private
var items: [Int] = []
func peek()->Int
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()
{
items.removeFirst()
}
mutating func push(_ data: Int)
{
items.insert(data, at: 0)
}
}
// Define edge of graph node
class AjlistNode
{
//Vertices id
var id: Int;
var next: AjlistNode? ;
init(_ id: Int)
{
self.id = id;
self.next = nil;
}
}
// Define node of graph
class GraphNode
{
//node key value
var data: Int;
var edge: AjlistNode? ;
init(_ data: Int)
{
self.data = data;
self.edge = nil;
}
}
class MyGraph
{
// Number of graph nodes
var size: Int;
var node: [GraphNode? ];
init(_ size: Int)
{
if (size < 0)
{
print("\n Invalid size of nodes ", size, " ");
self.size = 0;
self.node = Array(repeating: nil, count: 1);
}
else
{
self.size = size;
self.node = Array(repeating: nil, count: self.size);
var i: Int = 0;
//   Set graph node level and e
i = 0;
while (i < self.size)
{
self.node[i] = GraphNode(i);
i += 1;
}
}
}
//This function are connect nodes with one edge
func connectEdge(_ a: Int, _ b: Int)
{
if (self.size <= 0)
{
print("\n Graph have no nodes ");
return;
}
let newEdge: AjlistNode? = AjlistNode(b);
if (newEdge  != nil)
{
// Get first edge of [i] node
var edge: AjlistNode? = self.node[a]!.edge;
if (edge == nil)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
self.node[a]!.edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge!.next  != nil)
{
edge = edge!.next;
}
// Add edge at last position
edge!.next = newEdge;
}
}
else
{
print("\nMemory overflow, when connect a new edge from ( ", a, " to ", b, " ) nodes.");
}
}

// This function is add new edge
func addEdge(_ a: Int, _ b: Int)
{
if (self.size > 0 && a < self.size && b < self.size)
{
// connect edge
// a---->b
self.connectEdge(a, b);
}
else
{
//not valid Vertices
print("Invalid Node Vertices ", a ," ", b, terminator: "");
}
}
func printGraph()
{
if (self.size > 0)
{
var temp: AjlistNode? = nil;
// Loop controlling variable
var i = 0;
while (i < self.size)
{
print("\n Adjacency list of vertex ", i ," :", terminator: "");
// Get first edge of [i] node
temp = self.node[i]!.edge;
while (temp  != nil)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
print("  ", self.node[temp!.id]!.data, terminator: "");
temp = temp!.next;
}
i += 1;
}
}
else
{
print("Empty Graph Node", terminator: "");
}
}
// Set the default value in visited node
func resetDefault(_ visit:inout[Bool], _ n: Int)
{
var i = 0;
while (i < n)
{
visit[i] = false;
i += 1;
}
}
//  Find order of path in given current node
func fillOrder(_ current: Int,
_ visit:inout[Bool], _ record: inout Stack)
{
if (visit[current] == true)
{
return;
}
var temp = self.node[current]!.edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp  != nil)
{
self.fillOrder(temp!.id, &visit, &record);
// Visit to next edge
temp = temp!.next;
}
// Add the visited current node
record.push(current);
}
// Display graph nodes using DFS
func printPath(_ current: Int, _ visit: inout[Bool])
{
if (visit[current] == true)
{
return;
}
print(" ", current, terminator: "");
var temp = self.node[current]!.edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp  != nil)
{
self.printPath(temp!.id, &visit);
// Visit to next edge
temp = temp!.next;
}
}
// This function are add new edge
func transposeEdge(_ edges: AjlistNode? , _ point : Int)
{
var current : AjlistNode? = nil;
var e : AjlistNode? = edges;
while (e  != nil)
{
current = e;
// visit to next edge
e = e!.next;
// Make sure given node is is valid
if (current!.id < self.size)
{
current!.next = self.node[current!.id]!.edge;
//set node key value
self.node[current!.id]!.edge = current;
current!.id = point;
}
}
}
// This function are remove node edges
func transpose(_ point: Int)
{
if (point < self.size)
{
let e = self.node[point]!.edge;
// Segregating the edge
self.node[point]!.edge = nil;
// Recursively call to next node
self.transpose(point + 1);
// This method are combine new edges
self.transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
func scc()
{
if (self.size > 0)
{
var visit = Array(repeating: false, count: self.size);

// Use to collect visited node in reverse order
var record = Stack();
// Collect visited node information in record
var i = 0;
while (i < self.size)
{
if (visit[i] == false)
{
self.fillOrder(i, &visit, &record);
}
i += 1;
}
// Transpose the graph edges
self.transpose(0);
print("\n Strongly sonnected components ");
// initial no node visit
self.resetDefault(&visit, self.size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!record.isEmpty())
{
if (visit[record.peek()] == false)
{
// Dfs traverse
self.printPath(record.peek(), &visit);
print(terminator: "\n");
}
record.pop();
}
// Transpose the graph edges and back to original graph
self.transpose(0);
}
}
}
func main()
{
// 9 is number of nodes
let graph = MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
graph.printGraph();
// Print all strongly connected components
graph.scc();
}
main();``````

#### input

`````` Adjacency list of vertex  0  :   1
Adjacency list of vertex  1  :   2   4   5
Adjacency list of vertex  2  :   3   6
Adjacency list of vertex  3  :   2   7
Adjacency list of vertex  4  :   0   5
Adjacency list of vertex  5  :   6   8
Adjacency list of vertex  6  :   5
Adjacency list of vertex  7  :   3   6
Adjacency list of vertex  8  :
Strongly sonnected components
0  4  1
2  3  7
6  5
8``````
``````import java.util.Stack;
/*
Kotlin Program
Strongly connected components
*/
// Define edge of graph node
class AjlistNode
{
// Vertices id
var id: Int;
var next: AjlistNode ? ;
constructor(id: Int)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
class GraphNode
{
// node key value
var data: Int;
var edge: AjlistNode ? ;
constructor(data: Int)
{
this.data = data;
this.edge = null;
}
}
class MyGraph
{
var size: Int;
var node: Array<GraphNode?>;
constructor(size: Int)
{
if (size < 0)
{
print("\n Invalid size of nodes " + size + " \n");
this.size = 0;
this.node = Array(1)
{
null
};
}
else
{
this.size = size;
this.node = Array(this.size)
{
null
};
var i: Int = 0;
//   Set graph node level and e
while (i<this.size)
{
this.node[i] = GraphNode(i);
i += 1;
}
}
}
//This function are connect nodes with one edge
fun connectEdge(a: Int, b: Int): Unit
{
if (this.size <= 0)
{
print("\n Graph have no nodes \n");
return;
}
var newEdge: AjlistNode ? = AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
var edge: AjlistNode ? = this.node[a]?.edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a]?.edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge?.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge?.next = newEdge;
}
}
else
{
print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
}
}
// This is handles the request of connecting Edges between given node a to b
fun addEdge(a: Int, b: Int): Unit
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
this.connectEdge(a, b);
}
else
{
//not valid Vertices
print("Invalid Node Vertices " + a + " " + b);
}
}
fun printGraph(): Unit
{
if (this.size > 0)
{
var temp: AjlistNode ? ;
// Loop controlling variable
var i: Int = 0;
while (i < this.size)
{
print("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i]?.edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
print("  " + this.node[temp.id]?.data);
temp = temp.next;
}
i += 1;
}
}
else
{
print("Empty Graph Node");
}
}
// Set the default value in visited node
fun resetDefault(visit: Array < Boolean > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
visit[i] = false;
i += 1;
}
}
//  Find order of path in given current node
fun fillOrder(current: Int,
visit: Array < Boolean > , record: Stack < Int >  ): Unit
{
if (visit[current] == true)
{
return;
}
var temp: AjlistNode ? = this.node[current]?.edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
this.fillOrder(temp.id, visit, record);
// Visit to next edge
temp = temp.next;
}
// Add the visited current node
record.push(current);
}
// Display graph nodes using DFS
fun printPath(current: Int, visit: Array < Boolean > ): Unit
{
if (visit[current] == true)
{
return;
}
print(" " + current);
var temp: AjlistNode ? = this.node[current]?.edge;
// Active the visiting node status
visit[current] = true;
// iterating the nodes edges
while (temp != null)
{
this.printPath(temp.id, visit);
// Visit to next edge
temp = temp.next;
}
}
// This function are add new edge
fun transposeEdge(edges: AjlistNode ? , point : Int): Unit
{
var current: AjlistNode ? ;
var e: AjlistNode ? = edges;
while (e != null)
{
current = e;
// visit to next edge
e = e.next;
// Make sure given node is is valid
if (current.id < this.size)
{
current.next = this.node[current.id]?.edge;
// set node key value
this.node[current.id]?.edge = current;
current.id = point;
}
}
}
// This function are remove node edges
fun transpose(point: Int): Unit
{
if (point < this.size)
{
var e: AjlistNode ? = this.node[point]?.edge;
// Segregating the edge
this.node[point]?.edge = null;
// Recursively call to next node
this.transpose(point + 1);
// This method are combine new edges
this.transposeEdge(e, point);
}
}
// Handles the request of find strongly sonnected components
fun scc(): Unit
{
if (this.size > 0)
{
val visit: Array < Boolean > = Array(this.size)
{
false
};

// Use to collect visited node in reverse order
val record: Stack < Int > = Stack < Int > ();
// Collect visited node information in record
var i: Int = 0;
while (i < this.size)
{
if (visit[i] == false)
{
this.fillOrder(i, visit, record);
}
i += 1;
}
// Transpose the graph edges
this.transpose(0);
print("\n Strongly sonnected components \n");
// initial no node visit
this.resetDefault(visit, this.size);
// Execute loop until when record is not empty
// Traverse dfs in transpose graph
while (!record.empty())
{
if (visit[record.peek()] == false)
{
// Dfs traverse
this.printPath(record.peek(), visit);
print("\n");
}
record.pop();
}
// Transpose the graph edges and back to original graph
this.transpose(0);
}
}
}
fun main(args: Array < String > ): Unit
{
// 9 is number of nodes
val graph: MyGraph = MyGraph(9);
// Connected two node with Edges
// Print graph nodes and associative edges
graph.printGraph();
// Print all strongly connected components
graph.scc();
}``````

#### input

`````` Adjacency list of vertex 0 :  1
Adjacency list of vertex 1 :  2  4  5
Adjacency list of vertex 2 :  3  6
Adjacency list of vertex 3 :  2  7
Adjacency list of vertex 4 :  0  5
Adjacency list of vertex 5 :  6  8
Adjacency list of vertex 6 :  5
Adjacency list of vertex 7 :  3  6
Adjacency list of vertex 8 :
Strongly sonnected components
0 4 1
2 3 7
6 5
8``````

## 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.