Strongly Connected Components (SCC)
Definition
A Strongly Connected Component (SCC) is a specific group of nodes within a Directed Graph. In this group, you can start at any node and reach every other node in the same group by following the arrows (edges).
How it Works
Think of a directed graph like a city with one-way streets.
- The Rule: If you can drive from House A to House B and figure out a way to drive back from House B to House A, then A and B are in the same Strongly Connected Component.
- The Cycle: SCCs essentially define “cycles” or loops in a graph. If you can leave a group but never return, you have crossed into a different component.
- Partition: Every node in a directed graph belongs to exactly one SCC.
Real-World Analogy
City Neighborhoods:
Imagine a city divided into neighborhoods by highways.
- Inside a neighborhood (The SCC): The streets are a maze of one-way roads, but if you know the way, you can eventually get from any house to any other house within that neighborhood.
- Between neighborhoods: Once you take the highway exit to go to the “North Side,” you might not be able to come back to the “South Side” because the highway only goes one way. The “South Side” is one SCC, and the “North Side” is another.
Example
Graph:
- A rightarrow B
- B rightarrow C
- C rightarrow A (This creates a loop: A-B-C-A)
- B rightarrow D (One way street to D)
Components:
- {A, B, C}: You can travel between all of them.
- {D}: Once you are at D, you cannot go back to A, B, or C. D is its own component.
Code Example (Kosaraju’s Algorithm)
Note: This algorithm uses two passes of DFS to find these groups.
PythonJavaCC++
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
# Add directed edge
def add_edge(self, u, v):
self.graph[u].append(v)
# Step 1: DFS and fill stack by finish time
def fill_order(self, v, visited, stack):
visited.add(v)
for i in self.graph[v]:
if i not in visited:
self.fill_order(i, visited, stack)
stack.append(v)
# Step 2: Reverse graph
def get_transpose(self):
g = Graph(self.V)
for i in self.graph:
for j in self.graph[i]:
g.add_edge(j, i)
return g
# Step 3: DFS to print component
def dfs_print(self, v, visited):
visited.add(v)
print(v, end=" ")
for i in self.graph[v]:
if i not in visited:
self.dfs_print(i, visited)
# Main function for SCC
def print_sccs(self):
stack = []
visited = set()
# Fill stack
for i in range(self.V):
if i not in visited:
self.fill_order(i, visited, stack)
# Reverse graph
gr = self.get_transpose()
visited.clear()
# Process stack
while stack:
i = stack.pop()
if i not in visited:
gr.dfs_print(i, visited)
print()
# Example
g = Graph(5)
g.add_edge(1,0)
g.add_edge(0,2)
g.add_edge(2,1)
g.add_edge(0,3)
g.add_edge(3,4)
print("Strongly Connected Components:")
g.print_sccs()
import java.util.*;
class Graph {
int V;
LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void fillOrder(int v, boolean visited[], Stack<Integer> stack) {
visited[v] = true;
for (int n : adj[v])
if (!visited[n])
fillOrder(n, visited, stack);
stack.push(v);
}
Graph getTranspose() {
Graph g = new Graph(V);
for (int v = 0; v < V; v++)
for (int i : adj[v])
g.adj[i].add(v);
return g;
}
void DFSUtil(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");
for (int n : adj[v])
if (!visited[n])
DFSUtil(n, visited);
}
void printSCCs() {
Stack<Integer> stack = new Stack<>();
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
if (!visited[i])
fillOrder(i, visited, stack);
Graph gr = getTranspose();
Arrays.fill(visited, false);
while (!stack.empty()) {
int v = stack.pop();
if (!visited[v]) {
gr.DFSUtil(v, visited);
System.out.println();
}
}
}
public static void main(String[] args) {
Graph g = new Graph(5);
g.addEdge(1,0);
g.addEdge(0,2);
g.addEdge(2,1);
g.addEdge(0,3);
g.addEdge(3,4);
System.out.println("Strongly Connected Components:");
g.printSCCs();
}
}
#include <stdio.h>
#define V 5
int graph[V][V] = {0};
void addEdge(int u, int v) {
graph[u][v] = 1;
}
void dfs(int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < V; i++)
if (graph[v][i] && !visited[i])
dfs(i, visited);
}
int main() {
addEdge(1,0);
addEdge(0,2);
addEdge(2,1);
addEdge(0,3);
addEdge(3,4);
int visited[V] = {0};
printf("DFS Example (partial SCC logic):\n");
dfs(0, visited);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
class Graph {
public:
int V;
vector<vector<int>> adj;
Graph(int v) {
V = v;
adj.resize(v);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void dfs(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int i : adj[v])
if (!visited[i])
dfs(i, visited);
}
};
int main() {
Graph g(5);
g.addEdge(1,0);
g.addEdge(0,2);
g.addEdge(2,1);
g.addEdge(0,3);
g.addEdge(3,4);
vector<bool> visited(5,false);
cout << "DFS Example:" << endl;
g.dfs(0, visited);
return 0;
}
Complexity Analysis
- Time Complexity: O(V + E). We traverse the graph (DFS) twice and reverse it once. All are linear operations.
- Space Complexity: O(V). We need arrays to store visited status and the stack.
Use Cases
- Social Media Analysis: Finding tight-knit communities where everyone follows everyone else.
- Web Crawlers: Identifying “link farms” or groups of websites that link to each other to boost SEO rankings artificially.