Skip to main content

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;
        }
        // Create Adjacency node
        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);
        }
    }
    //Display Adjacency list of vertex
    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)
            {
                //add edge to node
                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);

                    // Add new line
                    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
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);
        graph.addEdge(1, 5);
        graph.addEdge(2, 3);
        graph.addEdge(2, 6);
        graph.addEdge(3, 2);
        graph.addEdge(3, 7);
        graph.addEdge(4, 0);
        graph.addEdge(4, 5);
        graph.addEdge(5, 6);
        graph.addEdge(5, 8);
        graph.addEdge(6, 5);
        graph.addEdge(7, 3);
        graph.addEdge(7, 6);
    
        // 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;
		}
		// Create Adjacency node
		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
	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
			cout << "Invalid Node Vertices " << a << " " << b;
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				//add edge to node
				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);
					// Add new line
					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
	graph->addEdge(0, 1);
	graph->addEdge(1, 2);
	graph->addEdge(1, 4);
	graph->addEdge(1, 5);
	graph->addEdge(2, 3);
	graph->addEdge(2, 6);
	graph->addEdge(3, 2);
	graph->addEdge(3, 7);
	graph->addEdge(4, 0);
	graph->addEdge(4, 5);
	graph->addEdge(5, 6);
	graph->addEdge(5, 8);
	graph->addEdge(6, 5);
	graph->addEdge(7, 3);
	graph->addEdge(7, 6);
	// 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;
		}
		// Create Adjacency node
		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);
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				//add edge to node
				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);
					// Add new line
					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
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(1, 5);
		graph.addEdge(2, 3);
		graph.addEdge(2, 6);
		graph.addEdge(3, 2);
		graph.addEdge(3, 7);
		graph.addEdge(4, 0);
		graph.addEdge(4, 5);
		graph.addEdge(5, 6);
		graph.addEdge(5, 8);
		graph.addEdge(6, 5);
		graph.addEdge(7, 3);
		graph.addEdge(7, 6);
		// 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;
		}
		// Create Adjacency node
		$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
	public	function addEdge($a, $b)
	{
		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);
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				//add edge to node
				$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);
					// Add new line
					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
	$graph->addEdge(0, 1);
	$graph->addEdge(1, 2);
	$graph->addEdge(1, 4);
	$graph->addEdge(1, 5);
	$graph->addEdge(2, 3);
	$graph->addEdge(2, 6);
	$graph->addEdge(3, 2);
	$graph->addEdge(3, 7);
	$graph->addEdge(4, 0);
	$graph->addEdge(4, 5);
	$graph->addEdge(5, 6);
	$graph->addEdge(5, 8);
	$graph->addEdge(6, 5);
	$graph->addEdge(7, 3);
	$graph->addEdge(7, 6);
	// 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;
		}
		// Create Adjacency node
		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
	addEdge(a, b)
	{
		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);
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				//add edge to node
				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);
					// Add new line
					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
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(1, 5);
	graph.addEdge(2, 3);
	graph.addEdge(2, 6);
	graph.addEdge(3, 2);
	graph.addEdge(3, 7);
	graph.addEdge(4, 0);
	graph.addEdge(4, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 8);
	graph.addEdge(6, 5);
	graph.addEdge(7, 3);
	graph.addEdge(7, 6);
	// 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
		
		#  Create Adjacency node
		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
	def addEdge(self, a, b) :
		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) :
				# add edge to node
				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)
					#  Add new line
					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
	graph.addEdge(0, 1)
	graph.addEdge(1, 2)
	graph.addEdge(1, 4)
	graph.addEdge(1, 5)
	graph.addEdge(2, 3)
	graph.addEdge(2, 6)
	graph.addEdge(3, 2)
	graph.addEdge(3, 7)
	graph.addEdge(4, 0)
	graph.addEdge(4, 5)
	graph.addEdge(5, 6)
	graph.addEdge(5, 8)
	graph.addEdge(6, 5)
	graph.addEdge(7, 3)
	graph.addEdge(7, 6)
	#  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_reader :id, :next
	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_reader :data, :edge
	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_reader :size, :node
	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

		#  Create Adjacency node
		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
	def addEdge(a, b) 
		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) 
				# add edge to node
				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)
					#  Add new line
					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
	graph.addEdge(0, 1)
	graph.addEdge(1, 2)
	graph.addEdge(1, 4)
	graph.addEdge(1, 5)
	graph.addEdge(2, 3)
	graph.addEdge(2, 6)
	graph.addEdge(3, 2)
	graph.addEdge(3, 7)
	graph.addEdge(4, 0)
	graph.addEdge(4, 5)
	graph.addEdge(5, 6)
	graph.addEdge(5, 8)
	graph.addEdge(6, 5)
	graph.addEdge(7, 3)
	graph.addEdge(7, 6)
	#  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;
		}
		// Create Adjacency node
		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);
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				//add edge to node
				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);
					// Add new line
					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
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(1, 5);
		graph.addEdge(2, 3);
		graph.addEdge(2, 6);
		graph.addEdge(3, 2);
		graph.addEdge(3, 7);
		graph.addEdge(4, 0);
		graph.addEdge(4, 5);
		graph.addEdge(5, 6);
		graph.addEdge(5, 8);
		graph.addEdge(6, 5);
		graph.addEdge(7, 3);
		graph.addEdge(7, 6);
		// 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;
		}
		// Create Adjacency node
		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: "");
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				//add edge to node
				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);
					// Add new line
					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
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(1, 5);
	graph.addEdge(2, 3);
	graph.addEdge(2, 6);
	graph.addEdge(3, 2);
	graph.addEdge(3, 7);
	graph.addEdge(4, 0);
	graph.addEdge(4, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 8);
	graph.addEdge(6, 5);
	graph.addEdge(7, 3);
	graph.addEdge(7, 6);
	// 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;
		}
		// Create Adjacency node
		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);
		}
	}
	//Display Adjacency list of vertex
	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)
			{
				// add edge to node
				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);
					// Add new line
					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
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(1, 5);
	graph.addEdge(2, 3);
	graph.addEdge(2, 6);
	graph.addEdge(3, 2);
	graph.addEdge(3, 7);
	graph.addEdge(4, 0);
	graph.addEdge(4, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 8);
	graph.addEdge(6, 5);
	graph.addEdge(7, 3);
	graph.addEdge(7, 6);
	// 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
Last updated on by Kalkicode




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.

New Comment