Brute Force Approach for Finding Strongly Connected Components
The simple method will be for each vertex i (which is not a part of any strongly component) find the vertices which will be the part of strongly connected component containing vertex i. Two vertex i and j will be in the same strongly connected component if they there is a directed path from vertex i to vertex j and vice-versa.
Let’s understand the approach with the help of following example:
- Starting with vertex 1. There is path from vertex 1 to vertex 2 and vice-versa. Similarly there is a path from vertex 1 to vertex 3 and vice versa. So, vertex 2 and 3 will be in the same Strongly Connected Component as vertex 1. Although there is directed path form vertex 1 to vertex 4 and vertex 5. But there is no directed path from vertex 4,5 to vertex 1 so vertex 4 and 5 won’t be in the same Strongly Connected Component as vertex 1. Thus Vertex 1,2 and 3 forms a Strongly Connected Component.
- For Vertex 2 and 3, there Strongly Connected Component has already been determined.
- For Vertex 4, there is a path from vertex 4 to vertex 5 but there is no path from vertex 5 to vertex 4. So vertex 4 and 5 won’t be in the Same Strongly Connected Component. So both Vertex 4 and Vertex 5 will be part of Single Strongly Connected Component.
- Hence there will be 3 Strongly Connected Component {1,2,3}, {4} and {5}.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
class GFG {
public:
// dfs Function to reach destination
bool dfs(int curr, int des, vector<vector<int> >& adj,
vector<int>& vis)
{
// If curr node is destination return true
if (curr == des) {
return true;
}
vis[curr] = 1;
for (auto x : adj[curr]) {
if (!vis[x]) {
if (dfs(x, des, adj, vis)) {
return true;
}
}
}
return false;
}
// To tell whether there is path from source to
// destination
bool isPath(int src, int des, vector<vector<int> >& adj)
{
vector<int> vis(adj.size() + 1, 0);
return dfs(src, des, adj, vis);
}
// Function to return all the strongly connected
// component of a graph.
vector<vector<int> > findSCC(int n,
vector<vector<int> >& a)
{
// Stores all the strongly connected components.
vector<vector<int> > ans;
// Stores whether a vertex is a part of any Strongly
// Connected Component
vector<int> is_scc(n + 1, 0);
vector<vector<int> > adj(n + 1);
for (int i = 0; i < a.size(); i++) {
adj[a[i][0]].push_back(a[i][1]);
}
// Traversing all the vertices
for (int i = 1; i <= n; i++) {
if (!is_scc[i]) {
// If a vertex i is not a part of any SCC
// insert it into a new SCC list and check
// for other vertices whether they can be
// thr part of thidl ist.
vector<int> scc;
scc.push_back(i);
for (int j = i + 1; j <= n; j++) {
// If there is a path from vertex i to
// vertex j and vice versa put vertex j
// into the current SCC list.
if (!is_scc[j] && isPath(i, j, adj)
&& isPath(j, i, adj)) {
is_scc[j] = 1;
scc.push_back(j);
}
}
// Insert the SCC containing vertex i into
// the final list.
ans.push_back(scc);
}
}
return ans;
}
};
// Driver Code Starts
int main()
{
GFG obj;
int V = 5;
vector<vector<int> > edges{
{ 1, 3 }, { 1, 4 }, { 2, 1 }, { 3, 2 }, { 4, 5 }
};
vector<vector<int> > ans = obj.findSCC(V, edges);
cout << "Strongly Connected Components are:\n";
for (auto x : ans) {
for (auto y : x) {
cout << y << " ";
}
cout << "\n";
}
}
import java.util.ArrayList;
import java.util.List;
class GFG {
// dfs Function to reach destination
boolean dfs(int curr, int des, List<List<Integer>> adj,
List<Integer> vis) {
// If curr node is destination return true
if (curr == des) {
return true;
}
vis.set(curr, 1);
for (int x : adj.get(curr)) {
if (vis.get(x) == 0) {
if (dfs(x, des, adj, vis)) {
return true;
}
}
}
return false;
}
// To tell whether there is path from source to
// destination
boolean isPath(int src, int des, List<List<Integer>> adj) {
List<Integer> vis = new ArrayList<>(adj.size() + 1);
for (int i = 0; i <= adj.size(); i++) {
vis.add(0);
}
return dfs(src, des, adj, vis);
}
// Function to return all the strongly connected
// component of a graph.
List<List<Integer>> findSCC(int n, List<List<Integer>> a) {
// Stores all the strongly connected components.
List<List<Integer>> ans = new ArrayList<>();
// Stores whether a vertex is a part of any Strongly
// Connected Component
List<Integer> is_scc = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
is_scc.add(0);
}
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (List<Integer> edge : a) {
adj.get(edge.get(0)).add(edge.get(1));
}
// Traversing all the vertices
for (int i = 1; i <= n; i++) {
if (is_scc.get(i) == 0) {
// If a vertex i is not a part of any SCC
// insert it into a new SCC list and check
// for other vertices whether they can be
// the part of this list.
List<Integer> scc = new ArrayList<>();
scc.add(i);
for (int j = i + 1; j <= n; j++) {
// If there is a path from vertex i to
// vertex j and vice versa, put vertex j
// into the current SCC list.
if (is_scc.get(j) == 0 && isPath(i, j, adj)
&& isPath(j, i, adj)) {
is_scc.set(j, 1);
scc.add(j);
}
}
// Insert the SCC containing vertex i into
// the final list.
ans.add(scc);
}
}
return ans;
}
}
public class Main {
public static void main(String[] args) {
GFG obj = new GFG();
int V = 5;
List<List<Integer>> edges = new ArrayList<>();
edges.add(new ArrayList<>(List.of(1, 3)));
edges.add(new ArrayList<>(List.of(1, 4)));
edges.add(new ArrayList<>(List.of(2, 1)));
edges.add(new ArrayList<>(List.of(3, 2)));
edges.add(new ArrayList<>(List.of(4, 5)));
List<List<Integer>> ans = obj.findSCC(V, edges);
System.out.println("Strongly Connected Components are:");
for (List<Integer> x : ans) {
for (int y : x) {
System.out.print(y + " ");
}
System.out.println();
}
}
}
// This code is contributed by shivamgupta310570
class GFG:
# dfs Function to reach destination
def dfs(self, curr, des, adj, vis):
# If current node is the destination, return True
if curr == des:
return True
vis[curr] = 1
for x in adj[curr]:
if not vis[x]:
if self.dfs(x, des, adj, vis):
return True
return False
# To tell whether there is a path from source to destination
def isPath(self, src, des, adj):
vis = [0] * (len(adj) + 1)
return self.dfs(src, des, adj, vis)
# Function to return all the strongly connected components of a graph.
def findSCC(self, n, a):
# Stores all the strongly connected components.
ans = []
# Stores whether a vertex is a part of any Strongly Connected Component
is_scc = [0] * (n + 1)
adj = [[] for _ in range(n + 1)]
for i in range(len(a)):
adj[a[i][0]].append(a[i][1])
# Traversing all the vertices
for i in range(1, n + 1):
if not is_scc[i]:
# If a vertex i is not a part of any SCC, insert it into a new SCC list
# and check for other vertices whether they can be part of this list.
scc = [i]
for j in range(i + 1, n + 1):
# If there is a path from vertex i to vertex j and vice versa,
# put vertex j into the current SCC list.
if not is_scc[j] and self.isPath(i, j, adj) and self.isPath(j, i, adj):
is_scc[j] = 1
scc.append(j)
# Insert the SCC containing vertex i into the final list.
ans.append(scc)
return ans
# Driver Code Starts
if __name__ == "__main__":
obj = GFG()
V = 5
edges = [
[1, 3], [1, 4], [2, 1], [3, 2], [4, 5]
]
ans = obj.findSCC(V, edges)
print("Strongly Connected Components are:")
for x in ans:
for y in x:
print(y, end=" ")
print()
# This code is contributed by shivamgupta310570
using System;
using System.Collections.Generic;
class GFG
{
// dfs Function to reach destination
public bool Dfs(int curr, int des, List<List<int>> adj, List<int> vis)
{
// If curr node is the destination, return true
if (curr == des)
{
return true;
}
vis[curr] = 1;
foreach (var x in adj[curr])
{
if (vis[x] == 0)
{
if (Dfs(x, des, adj, vis))
{
return true;
}
}
}
return false;
}
// To tell whether there is a path from source to destination
public bool IsPath(int src, int des, List<List<int>> adj)
{
var vis = new List<int>(adj.Count + 1);
for (int i = 0; i < adj.Count + 1; i++)
{
vis.Add(0);
}
return Dfs(src, des, adj, vis);
}
// Function to return all the strongly connected components of a graph
public List<List<int>> FindSCC(int n, List<List<int>> a)
{
// Stores all the strongly connected components
var ans = new List<List<int>>();
// Stores whether a vertex is a part of any Strongly Connected Component
var isScc = new List<int>(n + 1);
for (int i = 0; i < n + 1; i++)
{
isScc.Add(0);
}
var adj = new List<List<int>>(n + 1);
for (int i = 0; i < n + 1; i++)
{
adj.Add(new List<int>());
}
for (int i = 0; i < a.Count; i++)
{
adj[a[i][0]].Add(a[i][1]);
}
// Traversing all the vertices
for (int i = 1; i <= n; i++)
{
if (isScc[i] == 0)
{
// If a vertex i is not a part of any SCC
// insert it into a new SCC list and check
// for other vertices whether they can be
// the part of this list.
var scc = new List<int>();
scc.Add(i);
for (int j = i + 1; j <= n; j++)
{
// If there is a path from vertex i to
// vertex j and vice versa, put vertex j
// into the current SCC list.
if (isScc[j] == 0 && IsPath(i, j, adj) && IsPath(j, i, adj))
{
isScc[j] = 1;
scc.Add(j);
}
}
// Insert the SCC containing vertex i into
// the final list.
ans.Add(scc);
}
}
return ans;
}
}
// Driver Code Starts
class Program
{
static void Main(string[] args)
{
GFG obj = new GFG();
int V = 5;
List<List<int>> edges = new List<List<int>>
{
new List<int> { 1, 3 }, new List<int> { 1, 4 }, new List<int> { 2, 1 },
new List<int> { 3, 2 }, new List<int> { 4, 5 }
};
List<List<int>> ans = obj.FindSCC(V, edges);
Console.WriteLine("Strongly Connected Components are:");
foreach (var x in ans)
{
foreach (var y in x)
{
Console.Write(y + " ");
}
Console.WriteLine();
}
}
}
// This code is contributed by shivamgupta310570
class GFG {
// Function to reach the destination using DFS
dfs(curr, des, adj, vis) {
// If the current node is the destination, return true
if (curr === des) {
return true;
}
vis[curr] = 1;
for (let x of adj[curr]) {
if (!vis[x]) {
if (this.dfs(x, des, adj, vis)) {
return true;
}
}
}
return false;
}
// Check whether there is a path from source to destination
isPath(src, des, adj) {
const vis = new Array(adj.length + 1).fill(0);
return this.dfs(src, des, adj, vis);
}
// Function to find all strongly connected components of a graph
findSCC(n, a) {
// Stores all strongly connected components
const ans = [];
// Stores whether a vertex is part of any Strongly Connected Component
const is_scc = new Array(n + 1).fill(0);
const adj = new Array(n + 1).fill().map(() => []);
for (let i = 0; i < a.length; i++) {
adj[a[i][0]].push(a[i][1]);
}
// Traversing all the vertices
for (let i = 1; i <= n; i++) {
if (!is_scc[i]) {
// If a vertex i is not part of any SCC,
// insert it into a new SCC list and check
// for other vertices that can be part of this list.
const scc = [i];
for (let j = i + 1; j <= n; j++) {
// If there is a path from vertex i to
// vertex j and vice versa, put vertex j
// into the current SCC list.
if (!is_scc[j] && this.isPath(i, j, adj) && this.isPath(j, i, adj)) {
is_scc[j] = 1;
scc.push(j);
}
}
// Insert the SCC containing vertex i into the final list.
ans.push(scc);
}
}
return ans;
}
}
// Driver Code Starts
const obj = new GFG();
const V = 5;
const edges = [
[1, 3], [1, 4], [2, 1], [3, 2], [4, 5]
];
const ans = obj.findSCC(V, edges);
console.log("Strongly Connected Components are:");
for (let x of ans) {
console.log(x.join(" "));
}
// This code is contributed by shivamgupta310570
Output
Strongly Connected Components are: 1 2 3 4 5
Time complexity: O(n * (n + m)), because for each pair of vertices we are checking whether a path exists between them.
Auxiliary Space: O(N)
Strongly Connected Components
Strongly Connected Components (SCCs) are a fundamental concept in graph theory and algorithms. In a directed graph, a Strongly Connected Component is a subset of vertices where every vertex in the subset is reachable from every other vertex in the same subset by traversing the directed edges. Finding the SCCs of a graph can provide important insights into the structure and connectivity of the graph, with applications in various fields such as social network analysis, web crawling, and network routing. This tutorial will explore the definition, properties, and efficient algorithms for identifying Strongly Connected Components in graph data structures
Table of Content
- What is Strongly Connected Components (SCCs)?
- Why Strongly Connected Components (SCCs) are Important?
- Difference Between Connected and Strongly Connected Components (SCCs)
- Why conventional DFS method cannot be used to find strongly connected components?
- Connecting Two Strongly Connected Component by a Unidirectional Edge
- Brute Force Approach for Finding Strongly Connected Components
- Efficient Approach for Finding Strongly Connected Components (SCCs)
- 1. Kosaraju’s Algorithm:
- 2. Tarjan’s Algorithm:
- Conclusion
Contact Us