Connected Components in an Undirected Graph

Last Updated : 29 Oct, 2025

Given an undirected graph(the graph may contain one or more components) represented by an adjacency list adj[][], return all the connected components in any order.

Examples:

Input: adj[][] = [[2, 3], [2], [0, 1], [0], [5], [4]]

420046859

Output: [[0, 1, 2, 3], [4, 5]]
Explanation: There are 2 different connected components. They are {0, 1, 2, 3} and {4, 5}.

Input: adj[][] = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]

frame_3148

Output: [0, 1, 2, 3, 4]
Explanation: There is a single component, i.e., {0, 1, 2, 3, 4}.

Try it on GfG Practice
redirect icon

Table of Content

[Approach 1]: Using Depth first search (DFS)

In this approach, we perform a DFS once for every connected component in the graph. Each DFS call starting from an unvisited node explores and marks all nodes belonging to that component. Hence, for each DFS call, we can store the nodes of that component.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;

//Driver Code Ends

void dfs(vector<vector<int>>& adj, vector<bool>& visited, int s, vector<int>& res) {
    visited[s] = true;
    res.push_back(s);

    // Recursively visit all adjacent 
    // vertices that are not visited yet
    for (int i : adj[s]) {
        if (!visited[i]) {
            dfs(adj, visited, i, res);
        }
    }
}

vector<vector<int>> getComponents(vector<vector<int>>& adj) {
    int V = adj.size();
    vector<bool> visited(V, false);
    vector<vector<int>> res;

    // Loop through all vertices 
    // to handle all components
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            vector<int> component;
            dfs(adj, visited, i, component);
            res.push_back(component);
        }
    }

    return res;
}

//Driver Code Starts

void addEdge(vector<vector<int>>& adj, int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    
    // creating adjacency list
    addEdge(adj, 1, 2);
    addEdge(adj, 0, 3);
    addEdge(adj, 2, 0);
    addEdge(adj, 5, 4);

    // Perform DFS
    vector<vector<int>> res = getComponents(adj);

    for (auto& component : res) {
        for (int vertex : component) {
            cout << vertex << " ";
        }
        cout << endl;
    }

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.ArrayList;

public class GFG {
//Driver Code Ends

    private static void
    dfs(ArrayList<ArrayList<Integer>> adj,
           boolean[] visited, int s, ArrayList<Integer> res) {
        visited[s] = true;
        res.add(s);

        // Recursively visit all adjacent 
        // vertices that are not visited yet
        for (int i : adj.get(s)) {
            if (!visited[i]) {
                dfs(adj, visited, i, res);
            }
        }
    }

    public static ArrayList<ArrayList<Integer>>
    getComponents(ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        // Loop through all vertices 
        // to handle all components
        for (int i = 0; i < adj.size(); i++) {
            if (!visited[i]) {
                ArrayList<Integer> component = new ArrayList<>();
                dfs(adj, visited, i, component);
                res.add(component);
            }
        }

        return res;
    }

//Driver Code Starts

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
    
    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        // creating adjacency list
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 2, 0);
        addEdge(adj, 5, 4);
        
        // Perform DFS
        ArrayList<ArrayList<Integer>> res = getComponents(adj);

        for (ArrayList<Integer> component : res) {
            for (int vertex : component) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }
}
//Driver Code Ends
Python 
#Driver Code Starts
from collections import defaultdict

#Driver Code Ends

def dfs(adj, visited, s, res):
    visited[s] = True
    res.append(s)

    # Recursively visit all adjacent 
    # vertices that are not visited yet
    for i in adj[s]:
        if not visited[i]:
            dfs(adj, visited, i, res)

def getComponents(adj):
    V = len(adj)
    visited = [False] * V
    res = []

    # Loop through all vertices 
    # to handle all components
    for i in range(V):
        if not visited[i]:
            component = []
            dfs(adj, visited, i, component)
            res.append(component)

    return res

#Driver Code Starts

def addEdge(adj, u, v):
    adj[u].append(v)
    adj[v].append(u)
  
  
if __name__ == "__main__":
    V = 6
    adj = []
    
    # creating adjacency list
    for i in range(V):
        adj.append([])
        
    addEdge(adj, 1, 2)
    addEdge(adj, 0, 3)
    addEdge(adj, 2, 0)
    addEdge(adj, 5, 4)

    # Perform DFS
    res = getComponents(adj)

    for component in res:
        for vertex in component:
            print(vertex, end=" ")
        print()

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends

    private static void dfs(List<List<int>> adj, bool[] visited, int s, List<int> res) {
        visited[s] = true;
        res.Add(s);

        // Recursively visit all adjacent 
        // vertices that are not visited yet
        foreach (int i in adj[s]) {
            if (!visited[i]) {
                dfs(adj, visited, i, res);
            }
        }
    }

    public static List<List<int>> getComponents(List<List<int>> adj) {
        int V = adj.Count;
        bool[] visited = new bool[V];
        List<List<int>> res = new List<List<int>>();

        // Loop through all vertices 
        // to handle all components
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                List<int> component = new List<int>();
                dfs(adj, visited, i, component);
                res.Add(component);
            }
        }
        return res;
    }

//Driver Code Starts

    static void addEdge(List<List<int>> adj, int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }
    
    static void Main() {
        int V = 6;
        List<List<int>> adj = new List<List<int>>();
        
        // creating adjacency list
        for (int i = 0; i < V; i++)
            adj.Add(new List<int>());
            
        addEdge(adj, 1, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 2, 0);
        addEdge(adj, 5, 4);

        // Perform DFS
        List<List<int>> res = getComponents(adj);

        foreach (List<int> component in res) {
            foreach (int vertex in component) {
                Console.Write(vertex + " ");
            }
            Console.WriteLine();
        }
    }
}

//Driver Code Ends
JavaScript 
function dfs(adj, visited, s, res) {
    visited[s] = true;
    res.push(s);

    // Recursively visit all adjacent 
    // vertices that are not visited yet
    for (let i of adj[s]) {
        if (!visited[i]) {
            dfs(adj, visited, i, res);
        }
    }
}

function getComponents(adj) {
    const V = adj.length;
    const visited = new Array(V).fill(false);
    const res = [];

    // Loop through all vertices 
    // to handle all components
    for (let i = 0; i < V; i++) {
        if (!visited[i]) {
            const component = [];
            dfs(adj, visited, i, component);
            res.push(component);
        }
    }

    return res;
}


//Driver Code Starts
function addEdge(adj, u, v) {
    adj[u].push(v);
    adj[v].push(u);
}

// Driver code

let V = 6;
let adj = [];

// creating adjacency list
for (let i = 0; i < V; i++)
    adj.push([]);

addEdge(adj, 1, 2);
addEdge(adj, 0, 3);
addEdge(adj, 2, 0);
addEdge(adj, 5, 4);

// Perform DFS
const res = getComponents(adj);

for (const component of res) {
    console.log(component.join(" "));
}
//Driver Code Ends

Output
0 3 2 1 
4 5

Time complexity: O(V + E). We visit every vertex at most once and every edge is traversed at most once.
Auxiliary Space: O(V + E), since an extra visited array of size V is required, and recursive stack size.

[Approach 2]: Using Breadth first search (BFS) - O(V+E) Time and O(V) Space

The main idea is to perform a BFS once for every connected component in the graph. Each BFS call starting from an unvisited node explores and marks all nodes belonging to that component. Hence, for each BFS call, we can store the nodes of that component.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//Driver Code Ends

// BFS for a single connected component
void bfs(vector<vector<int>>& adj, int src, vector<bool>& visited, vector<int>& res) {
    queue<int> q;
    visited[src] = true;
    q.push(src);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        res.push_back(curr);

        // visit all the unvisited
        // neighbours of current node
        for (int x : adj[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
}

// BFS for all components (handles disconnected graphs)
vector<vector<int>> getComponents(vector<vector<int>>& adj) {
    int V = adj.size();
    vector<bool> visited(V, false);
    vector<vector<int>> res;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            vector<int> component;
            bfs(adj, i, visited, component);
            res.push_back(component);
        }
    }
    return res;
}

//Driver Code Starts

void addEdge(vector<vector<int>>& adj, int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    
    // creating adjacency list
    addEdge(adj, 1, 2);
    addEdge(adj, 0, 3);
    addEdge(adj, 2, 0);
    addEdge(adj, 5, 4);

    vector<vector<int>> res = getComponents(adj);

    for (auto& component : res) {
        for (int vertex : component) {
            cout << vertex << " ";
        }
        cout << endl;
    }

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

class GfG {
//Driver Code Ends

    // BFS for a single connected component
    static void bfs(ArrayList<ArrayList<Integer>> adj, int src, boolean[] visited, ArrayList<Integer> res) {
        Queue<Integer> q = new LinkedList<>();
        visited[src] = true;
        q.add(src);

        while (!q.isEmpty()) {
            int curr = q.poll();
            res.add(curr);

            // visit all the unvisited
            // neighbours of current node
            for (int x : adj.get(curr)) {
                if (!visited[x]) {
                    visited[x] = true;
                    q.add(x);
                }
            }
        }
    }

    // BFS for all components (handles disconnected graphs)
    static ArrayList<ArrayList<Integer>> getComponents(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        boolean[] visited = new boolean[V];
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                ArrayList<Integer> component = new ArrayList<>();
                bfs(adj, i, visited, component);
                res.add(component);
            }
        }
        return res;
    }

//Driver Code Starts

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
    
    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        // creating adjacency list
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 2, 0);
        addEdge(adj, 5, 4);

        ArrayList<ArrayList<Integer>> res = getComponents(adj);

        for (ArrayList<Integer> component : res) {
            for (int vertex : component) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }
}
//Driver Code Ends
Python 
#Driver Code Starts
from collections import deque

#Driver Code Ends

# BFS for a single connected component
def bfs(adj, src, visited, res):
    q = deque()
    visited[src] = True
    q.append(src)

    while q:
        curr = q.popleft()
        res.append(curr)

        # visit all the unvisited
        # neighbours of current node
        for x in adj[curr]:
            if not visited[x]:
                visited[x] = True
                q.append(x)

# BFS for all components (handles disconnected graphs)
def getComponents(adj):
    V = len(adj)
    visited = [False] * V
    res = []

    # Loop through all vertices
    # to handle all components
    for i in range(V):
        if not visited[i]:
            component = []
            bfs(adj, i, visited, component)
            res.append(component)

    return res

#Driver Code Starts

def addEdge(adj, u, v):
    adj[u].append(v)
    adj[v].append(u)
  
  
if __name__ == "__main__":
    V = 6
    adj = []
    
    # creating adjacency list
    for i in range(V):
        adj.append([])
        
    addEdge(adj, 1, 2)
    addEdge(adj, 0, 3)
    addEdge(adj, 2, 0)
    addEdge(adj, 5, 4)
    
    # Perform BFS
    res = getComponents(adj)

    for component in res:
        for vertex in component:
            print(vertex, end=" ")
        print()
#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {
//Driver Code Ends

    // BFS for a single connected component
    private static void bfs(List<List<int>> adj, 
    int src, bool[] visited, List<int> res) {
        Queue<int> q = new Queue<int>();
        visited[src] = true;
        q.Enqueue(src);

        while (q.Count > 0) {
            int curr = q.Dequeue();
            res.Add(curr);

            // visit all the unvisited
            // neighbours of current node
            foreach (int x in adj[curr]) {
                if (!visited[x]) {
                    visited[x] = true;
                    q.Enqueue(x);
                }
            }
        }
    }

    // BFS for all components (handles disconnected graphs)
    public static List<List<int>> getComponents(List<List<int>> adj) {
        int V = adj.Count;
        bool[] visited = new bool[V];
        List<List<int>> res = new List<List<int>>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                List<int> component = new List<int>();
                bfs(adj, i, visited, component);
                res.Add(component);
            }
        }
        return res;
    }

//Driver Code Starts

    static void addEdge(List<List<int>> adj, int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }
    
    static void Main() {
        int V = 6;
        List<List<int>> adj = new List<List<int>>();
        
        // creating adjacency list
        for (int i = 0; i < V; i++)
            adj.Add(new List<int>());
            
        addEdge(adj, 1, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 2, 0);
        addEdge(adj, 5, 4);

        List<List<int>> res = getComponents(adj);

        foreach (List<int> component in res) {
            foreach (int vertex in component) {
                Console.Write(vertex + " ");
            }
            Console.WriteLine();
        }
    }
}

//Driver Code Ends
JavaScript 
// BFS for a single connected component
function bfs(adj, src, visited, res) {
    const q = [];
    visited[src] = true;
    q.push(src);

    while (q.length > 0) {
        const curr = q.shift();
        res.push(curr);

        // visit all the unvisited
        // neighbours of current node
        for (const x of adj[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
}

// BFS for all components (handles disconnected graphs)
function getComponents(adj) {
    const V = adj.length;
    const visited = new Array(V).fill(false);
    const res = [];

    // Loop through all vertices
    // to handle all components
    for (let i = 0; i < V; i++) {
        if (!visited[i]) {
            const component = [];
            bfs(adj, i, visited, component);
            res.push(component);
        }
    }

    return res;
}


//Driver Code Starts
function addEdge(adj, u, v) {
    adj[u].push(v);
    adj[v].push(u);
}

// Driver code

let V = 6;
let adj = [];

// creating adjacency list
for (let i = 0; i < V; i++)
    adj.push([]);

addEdge(adj, 1, 2);
addEdge(adj, 0, 3);
addEdge(adj, 2, 0);
addEdge(adj, 5, 4);

// Perform BFS
const res = getComponents(adj);

for (const component of res) {
    console.log(component.join(" "));
}
//Driver Code Ends

Output
0 3 2 1 
4 5

[Approach 3]: Using Disjoint Set Union (DSU) - O(V+E) Time and O(V) Space

The idea is to use Disjoint Set Union (DSU) to find all connected components in the graph. We unite the vertices connected by edges using union function and finally we get different vertices belonging to different components.

C++ 
//Driver Code Starts
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

//Driver Code Ends

// DSU class
class DSU {
public:
    vector<int> parent;
    DSU(int n) {
        parent.resize(n);
        // Each node is its own parent initially
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    // Find with path compression
    int findParent(int u) {
        if (u == parent[u]) return u;
        return parent[u] = findParent(parent[u]);
    }

    // Union the sets of u and v
    void unite(int u, int v) {
        int pu = findParent(u);
        int pv = findParent(v);
        if (pu == pv) return;
        parent[pu] = pv;
    }
};

// Function to find all connected components using DSU
vector<vector<int>> getComponents(vector<vector<int>>& adj) {
    int V = adj.size();
    DSU dsu(V);
    
    // unite components on the basis of edges
    for (int i = 0; i < V; i++) {
        for (int next : adj[i]) {
            dsu.unite(i, next);
        }
    }

    unordered_map<int, vector<int>> resMap;
    for (int i = 0; i < V; i++) {
        int par = dsu.findParent(i);
        resMap[par].push_back(i);
    }

    vector<vector<int>> res;
    for (auto& [p, nodes] : resMap)
        res.push_back(nodes);

    return res;
}

//Driver Code Starts

void addEdge(vector<vector<int>>& adj, int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    
    // creating adjacency list
    addEdge(adj, 1, 2);
    addEdge(adj, 0, 3);
    addEdge(adj, 2, 0);
    addEdge(adj, 5, 4);

    vector<vector<int>> res = getComponents(adj);

    for (auto& component : res) {
        for (int vertex : component) {
            cout << vertex << " ";
        }
        cout << endl;
    }

    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.*;

//Driver Code Ends

// DSU class
class DSU {
    int[] parent;
    public DSU(int n) {
        parent = new int[n];

        // Each node is its own parent initially
        for (int i = 0; i < n; i++) {
            parent[i] = i;  
        }
    }

    // Find with path compression
    int findParent( int u ) {
        if( u == parent[u]) return u;
        return parent[u] = findParent(parent[u]);
    }
    
    // Union the sets of u and v 
    void unite( int u, int v ) {
        int pu = findParent(u);
        int pv = findParent(v);
        if( pu == pv ) return;
        parent[pu] = pv;
    }
}

class GFG {

    // Function to find all connected components using DSU
    static ArrayList<ArrayList<Integer>> getComponents(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        
        DSU dsu = new DSU(V);
        for( int i = 0; i < V; i++ ) {
            for( int next : adj.get(i)) {
                dsu.unite(i, next);
            }
        }
        Map<Integer, ArrayList<Integer>> resMap = new HashMap<>();
        
        // unite components on the basis of edges
        for( int i = 0; i < V; i++ ) {
            resMap.computeIfAbsent(dsu.findParent(i), 
            k -> new ArrayList<>()).add(i);
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for( int par : resMap.keySet()) {
            res.add(resMap.get(par));
        }
        return res;
    }

//Driver Code Starts

    static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
    
    public static void main(String[] args) {
        int V = 6;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        // creating adjacency list
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 2, 0);
        addEdge(adj, 5, 4);

        ArrayList<ArrayList<Integer>> res = getComponents(adj);

        for (ArrayList<Integer> component : res) {
            for (int vertex : component) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }
}

//Driver Code Ends
Python 
# DSU class
class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]  # Each node is its own parent initially

    # Find with path compression
    def find_parent(self, u):
        if u == self.parent[u]:
            return u
        self.parent[u] = self.find_parent(self.parent[u])
        return self.parent[u]

    # Union the sets of u and v
    def unite(self, u, v):
        pu = self.find_parent(u)
        pv = self.find_parent(v)
        if pu == pv:
            return
        self.parent[pu] = pv


# Function to find all connected components using DSU
def getComponents(adj):
    V = len(adj)
    dsu = DSU(V)

    # unite components on the basis of edges
    for i in range(V):
        for nxt in adj[i]:
            dsu.unite(i, nxt)

    res_map = {}
    for i in range(V):
        par = dsu.find_parent(i)
        res_map.setdefault(par, []).append(i)

    res = list(res_map.values())
    return res


#Driver Code Starts
def addEdge(adj, u, v):
    adj[u].append(v)
    adj[v].append(u)
  
  
if __name__ == "__main__":
    V = 6
    adj = []
    
    # creating adjacency list
    for i in range(V):
        adj.append([])
        
    addEdge(adj, 1, 2)
    addEdge(adj, 0, 3)
    addEdge(adj, 2, 0)
    addEdge(adj, 5, 4)
    
    # Perform BFS
    res = getComponents(adj)

    for component in res:
        for vertex in component:
            print(vertex, end=" ")
        print()
#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

//Driver Code Ends

// DSU class
class DSU {
    int[] parent;
    public DSU(int n) {
        parent = new int[n];
        // Each node is its own parent initially
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    // Find with path compression
    int findParent(int u) {
        if (u == parent[u]) return u;
        return parent[u] = findParent(parent[u]);
    }

    // Union the sets of u and v
    public void unite(int u, int v) {
        int pu = findParent(u);
        int pv = findParent(v);
        if (pu == pv) return;
        parent[pu] = pv;
    }

    public int getParent(int u) => findParent(u);
}

class GFG {
    // Function to find all connected components using DSU
    static List<List<int>> getComponents(List<List<int>> adj) {
        int V = adj.Count;
        DSU dsu = new DSU(V);

        for (int i = 0; i < V; i++) {
            foreach (int next in adj[i])
                dsu.unite(i, next);
        }

        Dictionary<int, List<int>> resMap = new Dictionary<int, List<int>>();
        
        // unite components on the basis of edges
        for (int i = 0; i < V; i++) {
            int par = dsu.getParent(i);
            if (!resMap.ContainsKey(par))
                resMap[par] = new List<int>();
            resMap[par].Add(i);
        }

        List<List<int>> res = new List<List<int>>();
        foreach (var kv in resMap.Values)
            res.Add(kv);

        return res;
    }

//Driver Code Starts
    
    static void addEdge(List<List<int>> adj, int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    static void Main() {
        int V = 6;
        List<List<int>> adj = new List<List<int>>();
        
        // creating adjacency list
        for (int i = 0; i < V; i++)
            adj.Add(new List<int>());
            
        addEdge(adj, 1, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 2, 0);
        addEdge(adj, 5, 4);
        
        List<List<int>> res = getComponents(adj);

        foreach (List<int> component in res) {
            foreach (int vertex in component) {
                Console.Write(vertex + " ");
            }
            Console.WriteLine();
        }
    }
}

//Driver Code Ends
JavaScript 
// DSU class
class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }

  // Find with path compression
  findParent(u) {
    if (u === this.parent[u]) return u;
    return (this.parent[u] = this.findParent(this.parent[u]));
  }

  // Union the sets of u and v
  unite(u, v) {
    const pu = this.findParent(u);
    const pv = this.findParent(v);
    if (pu === pv) return;
    this.parent[pu] = pv;
  }
}

// Function to find all connected components using DSU
function getComponents(adj) {
  const V = adj.length;
  const dsu = new DSU(V);

  for (let i = 0; i < V; i++) {
    for (const next of adj[i]) {
      dsu.unite(i, next);
    }
  }

  const resMap = new Map();
  
  // unite components on the basis of edges
  for (let i = 0; i < V; i++) {
    const par = dsu.findParent(i);
    if (!resMap.has(par)) resMap.set(par, []);
    resMap.get(par).push(i);
  }

  return Array.from(resMap.values());
}


//Driver Code Starts
function addEdge(adj, u, v) {
    adj[u].push(v);
    adj[v].push(u);
}

// Driver code

let V = 6;
let adj = [];

// creating adjacency list
for (let i = 0; i < V; i++)
    adj.push([]);

addEdge(adj, 1, 2);
addEdge(adj, 0, 3);
addEdge(adj, 2, 0);
addEdge(adj, 5, 4);

// Perform BFS
const res = getComponents(adj);

for (const component of res) {
    console.log(component.join(" "));
}
//Driver Code Ends

Output
4 5 
0 1 2 3
Comment
Article Tags:
Graph
DSA
BFS
DFS
+1 More

Explore