## Algorithm

Strongly Connected Components (SCCs) are a concept in graph theory that arise in the context of directed graphs. In a directed graph, an SCC is a subset of vertices in which there is a directed path from every vertex to every other vertex within the subset.

Formally, an SCC in a directed graph G is a maximal set of vertices C 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 within C.

Finding strongly connected components is a fundamental algorithmic problem with applications in various areas, including compiler optimization, network analysis, and modeling systems with concurrency.

The most common algorithm used to find strongly connected components is Kosaraju's algorithm, which consists of two depth-first search (DFS) passes. Here's a high-level overview of the algorithm:

1. First Pass (DFS on Reverse Graph):

• Perform a DFS on the reverse graph (i.e., all edges reversed) to compute finishing times for each vertex. This step assigns a postorder number to each vertex.
2. Second Pass (DFS on Original Graph):

• Start DFS on the original graph in decreasing order of finishing times obtained from the first pass.
• Each DFS traversal from an unvisited vertex in this order identifies a strongly connected component.

The algorithm's correctness relies on the fact that the second DFS pass can reveal the strongly connected components by exploring vertices in reverse topological order based on finishing times.

The time complexity of Kosaraju's algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Other algorithms for finding strongly connected components include Tarjan's algorithm, which also uses a single DFS pass.

In summary, strongly connected components provide a way to analyze the connectivity structure of directed graphs and can be efficiently computed using algorithms like Kosaraju's or Tarjan's.

## Code Examples

### #1 Strongly Connected Components implement in Python

Code - Python Programming

from collections import defaultdict

class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.graph = defaultdict(list)

self.graph[u].append(v)

def dfs(self, vertex, visited, stack):
visited[vertex] = True
for neighbor in self.graph[vertex]:
if not visited[neighbor]:
self.dfs(neighbor, visited, stack)
stack.append(vertex)

def transpose(self):
transposed_graph = Graph(self.vertices)
for vertex in self.graph:
for neighbor in self.graph[vertex]:
return transposed_graph

def dfs_scc(self, vertex, visited, scc):
visited[vertex] = True
scc.append(vertex)
for neighbor in self.graph[vertex]:
if not visited[neighbor]:
self.dfs_scc(neighbor, visited, scc)

def kosaraju_scc(self):
stack = []
visited = [False] * self.vertices

for vertex in range(self.vertices):
if not visited[vertex]:
self.dfs(vertex, visited, stack)

transposed_graph = self.transpose()

visited = [False] * self.vertices
strongly_connected_components = []

while stack:
vertex = stack.pop()
if not visited[vertex]:
scc = []
transposed_graph.dfs_scc(vertex, visited, scc)
strongly_connected_components.append(scc)

return strongly_connected_components

# Example usage:
g = Graph(5)

scc_result = g.kosaraju_scc()
print("Strongly Connected Components:")
print(scc_result)

Copy The Code &

### #2 Strongly Connected Components implement in Java

Code - Java Programming

import java.util.*;

class Graph {
private int V;

Graph(int v) {
V = v;
for (int i = 0; i  <  v; ++i)
}

void addEdge(int v, int w) {
}

void fillOrder(int v, boolean visited[], Stack < Integer> stack) {
visited[v] = true;

if (!visited[neighbor])
fillOrder(neighbor, visited, stack);

stack.push(v);
}

Graph getTranspose() {
Graph g = new Graph(V);
for (int v = 0; v  <  V; v++) {
for (Integer neighbor : adj[v]) {
}
}
return g;
}

void DFS(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");

for (Integer neighbor : adj[v]) {
if (!visited[neighbor]) {
DFS(neighbor, visited);
}
}
}

void printSCCs() {
Stack < Integer> stack = new Stack<>();

boolean[] visited = new boolean[V];
for (int i = 0; i  <  V; i++)
visited[i] = false;

for (int i = 0; i  <  V; i++)
if (!visited[i])
fillOrder(i, visited, stack);

Graph transposedGraph = getTranspose();

for (int i = 0; i  <  V; i++)
visited[i] = false;

while (!stack.isEmpty()) {
int v = stack.pop();

if (!visited[v]) {
transposedGraph.DFS(v, visited);
System.out.println();
}
}
}

public static void main(String args[]) {
Graph g = new Graph(5);

System.out.println("Strongly Connected Components:");
g.printSCCs();
}
}

Copy The Code &

### #3 Strongly Connected Components implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 1000

struct Node {
int data;
struct Node* next;
};

struct Graph {
int vertices;
};

struct Stack {
int* items;
int top;
};

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

struct Stack* createStack(int capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->items = (int*)malloc(sizeof(int) * capacity);
stack->top = -1;
return stack;
}

struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->vertices = vertices;
graph->adjacency_list = (struct Node**)malloc(sizeof(struct Node*) * vertices);

for (int i = 0; i  <  vertices; ++i) {
}

return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
}

void fillOrder(struct Graph* graph, int vertex, int* visited, struct Stack* stack) {
visited[vertex] = 1;

while (current != NULL) {
if (!visited[current->data]) {
fillOrder(graph, current->data, visited, stack);
}
current = current->next;
}

push(stack, vertex);
}

struct Graph* getTranspose(struct Graph* graph) {
struct Graph* transposedGraph = createGraph(graph->vertices);

for (int v = 0; v  <  graph->vertices; v++) {
while (current != NULL) {
current = current->next;
}
}

return transposedGraph;
}

void DFS(struct Graph* graph, int vertex, int* visited) {
visited[vertex] = 1;
printf("%d ", vertex);

while (current != NULL) {
if (!visited[current->data]) {
DFS(graph, current->data, visited);
}
current = current->next;
}
}

void printSCCs(struct Graph* graph) {
struct Stack* stack = createStack(graph->vertices);
int* visited = (int*)malloc(sizeof(int) * graph->vertices);

for (int i = 0; i  <  graph->vertices; i++) {
visited[i] = 0;
}

for (int i = 0; i  <  graph->vertices; i++) {
if (!visited[i]) {
fillOrder(graph, i, visited, stack);
}
}

struct Graph* transposedGraph = getTranspose(graph);

for (int i = 0; i  <  graph->vertices; i++) {
visited[i] = 0;
}

while (stack->top != -1) {
int vertex = pop(stack);

if (!visited[vertex]) {
printf("SCC: ");
DFS(transposedGraph, vertex, visited);
printf("\n");
}
}
}

void push(struct Stack* stack, int item) {
stack->items[++stack->top] = item;
}

int pop(struct Stack* stack) {
return stack->items[stack->top--];
}

int main() {
int vertices, edges;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);

struct Graph* graph = createGraph(vertices);

printf("Enter the number of edges: ");
scanf("%d", &edges);

printf("Enter the edges (source destination):\n");
for (int i = 0; i  <  edges; i++) {
int src, dest;
scanf("%d %d", &src, &dest);
}

printf("Strongly Connected Components:\n");
printSCCs(graph);

return 0;
}

Copy The Code &

### #4 Strongly Connected Components implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Graph {
int V; // Number of vertices

public:
Graph(int vertices) : V(vertices), adj(vertices) {}

// Add edge to the graph
void addEdge(int u, int v) {
}

// DFS to fill stack with vertices in increasing order of finishing times
void fillOrder(int v, vector < bool>& visited, stack<int>& stack) {
visited[v] = true;
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
fillOrder(neighbor, visited, stack);
}
}
stack.push(v);
}

// Transpose the graph (reverse all edges)
Graph getTranspose() {
Graph gT(V);
for (int v = 0; v  <  V; ++v) {
for (int neighbor : adj[v]) {
}
}
return gT;
}

// DFS to explore a SCC
void DFS(int v, vector < bool>& visited, vector<int>& scc) {
visited[v] = true;
scc.push_back(v);
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
DFS(neighbor, visited, scc);
}
}
}

// Function to find strongly connected components
void printSCCs() {
stack < int> stack;
vector<bool> visited(V, false);

// Fill vertices in stack according to their finishing times
for (int v = 0; v  <  V; ++v) {
if (!visited[v]) {
fillOrder(v, visited, stack);
}
}

// Transpose the graph
Graph gT = getTranspose();

// Reset visited array for the second DFS
fill(visited.begin(), visited.end(), false);

// Process vertices in decreasing order of finishing times
while (!stack.empty()) {
int v = stack.top();
stack.pop();

if (!visited[v]) {
vector<int> scc;
gT.DFS(v, visited, scc);

// Print the current SCC
cout << "SCC:";
for (int vertex : scc) {
cout << " " << vertex;
}
cout << endl;
}
}
}
};

int main() {
// Create a graph
Graph g(5);

// Print SCCs
cout << "Strongly Connected Components:\n";
g.printSCCs();

return 0;
}

Copy The Code &