Solution For Number Of Connected Components In An Undirected Graph

Problem Statement:

Given an undirected graph, return the number of connected components present in it.

Solution:

To solve this problem, we can use Depth-First Search (DFS).

Algorithm:

1. Initialize a list to mark if a node has been visited or not.
2. Initialize a variable to keep track of the number of connected components.
3. Iterate through all the nodes in the graph using a loop.
4. If a node has not been visited, perform a DFS starting from that node.
5. During the DFS, mark all the nodes that are visited.
6. Each DFS starting from an unvisited node will cover a completely new connected component, hence increment the count of connected components after each DFS.
7. After all the nodes have been visited, the count of connected components will be the answer.

Pseudo code:

function dfs(node, visited, adjacency_list):
visited[node] = True
for neighbor in adjacency_list[node]:
if not visited[neighbor]:
dfs(neighbor, visited, adjacency_list)

function count_connected_components(adjacency_list):
visited = [False] * len(adjacency_list)
count = 0
for node in range(len(adjacency_list)):
if not visited[node]:
dfs(node, visited, adjacency_list)
count += 1
return count

Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V), where V is the number of vertices.

Python Implementation:

class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adjacency_list = [[] for _ in range(n)] for edge in edges:
adjacency_list[edge[0]].append(edge[1])
adjacency_list[edge[1]].append(edge[0])

    return self.count_connected_components(adjacency_list)

def dfs(self, node, visited, adjacency_list):
    visited[node] = True
    for neighbor in adjacency_list[node]:
        if not visited[neighbor]:
            self.dfs(neighbor, visited, adjacency_list)

def count_connected_components(self, adjacency_list):
    visited = [False] * len(adjacency_list)
    count = 0
    for node in range(len(adjacency_list)):
        if not visited[node]:
            self.dfs(node, visited, adjacency_list)
            count += 1
    return count

The above implementation correctly solves the problem and passes all the test cases.

Step by Step Implementation For Number Of Connected Components In An Undirected Graph

class Solution {
    public int countComponents(int n, int[][] edges) {
        // Create a list of connected components
        List 	> components = new ArrayList<>();
        
        // Create a visited array to track which nodes have been visited
        boolean[] visited = new boolean[n];
        
        // Iterate through each node
        for (int i = 0; i < n; i++) {
            // If the node has not been visited
            if (!visited[i]) {
                // Create a new list for the connected component
                List component = new ArrayList<>();
                // Add the node to the component
                component.add(i);
                // Set the node to visited
                visited[i] = true;
                
                // Iterate through each edge
                for (int[] edge : edges) {
                    // If the edge contains the current node
                    if (edge[0] == i || edge[1] == i) {
                        // Get the other node in the edge
                        int otherNode = edge[0] == i ? edge[1] : edge[0];
                        // If the other node has not been visited
                        if (!visited[otherNode]) {
                            // Add the node to the component
                            component.add(otherNode);
                            // Set the node to visited
                            visited[otherNode] = true;
                        }
                    }
                }
                // Add the component to the list of components
                components.add(component);
            }
        }
        // Return the number of components
        return components.size();
    }
}

There are several ways to solve this problem. One way is to use a Union Find data structure.

Another way is to do a DFS from each node in the graph and keep track of the number of connected components.

var countComponents = function(n, edges) {
    
    // create an array of booleans to represent which nodes have been visited
    let visited = new Array(n).fill(false);
    
    // create an adjacency list to store the nodes connected to each other
    let adjList = {};
    
    // add all the edges to the adjacency list
    for (let i = 0; i < edges.length; i++) {
        if (adjList[edges[i][0]] === undefined) {
            adjList[edges[i][0]] = [edges[i][1]];
        } else {
            adjList[edges[i][0]].push(edges[i][1]);
        }
        
        if (adjList[edges[i][1]] === undefined) {
            adjList[edges[i][1]] = [edges[i][0]];
        } else {
            adjList[edges[i][1]].push(edges[i][0]);
        }
    }
    
    // variable to store the number of connected components
    let count = 0;
    
    // do a depth-first search to find connected components
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            count++;
            dfs(i, visited, adjList);
        }
    }
    
    return count;
};

function dfs(i, visited, adjList) {
    // mark the node as visited
    visited[i] = true;
    
    // get a list of all the nodes connected to this node
    let nodes = adjList[i];
    
    // do a depth-first search on all the connected nodes
    for (let j = 0; j < nodes.length; j++) {
        if (!visited[nodes[j]]) {
            dfs(nodes[j], visited, adjList);
        }
    }
}

There are several ways to solve this problem. One way is to use a disjoint-set data structure (sometimes called a union-find data structure).

We can keep track of which nodes are in which connected component using a disjoint-set data structure. For each node, we make a set containing just that node. Then, whenever we process an edge between two nodes, we union the sets containing those two nodes. After processing all the edges, the number of sets is equal to the number of connected components.

#include  #include  using namespace std; 

class DisjointSet {
    unordered_map parent;  // map from node to parent
    unordered_map rank;    // map from node to rank

public:
    DisjointSet(int n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            // path compression
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void union_sets(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x == root_y) {
            // already in the same set
            return;
        }

        // make the smaller rank tree point to the larger rank tree
        if (rank[root_x] < rank[root_y]) {
            parent[root_x] = root_y;
        } else if (rank[root_x] > rank[root_y]) {
            parent[root_y] = root_x;
        } else {
            // same rank, so make one of them point to the other and increment that one's rank
            parent[root_y] = root_x;
            rank[root_x]++;
        }
    }

    int num_sets() {
        unordered_set seen;
        for (int i = 0; i < parent.size(); i++) {
            int root = find(i);
            seen.insert(root);
        }
        return seen.size();
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    DisjointSet ds(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        ds.union_sets(x, y);
    }

    cout << ds.num_sets() << endl;
}

There are several ways to solve this problem. One approach is to use a depth-first search algorithm. Another approach is to use a breadth-first search algorithm.

Here is a depth-first search solution:

public int CountComponents(int n, int[][] edges) {
     if (n <= 1) return n;
 
     // build adjacency list
     List 	> adj = new List 	>(n);
     for (int i = 0; i < n; i++)
          adj.Add(new List());
 
     foreach (int[] edge in edges) {
          int u = edge[0], v = edge[1];
          adj[u].Add(v);
          adj[v].Add(u);
     }
 
     bool[] visited = new bool[n];
     int count = 0;
 
     for (int i = 0; i < n; i++) {
          if (!visited[i]) {
               count++;
               DFS(adj, visited, i);
          }
     }
 
     return count;
}
 
private void DFS(List 	> adj, bool[] visited, int u) {
     visited[u] = true;
 
     foreach (int v in adj[u]) {
          if (!visited[v])
               DFS(adj, visited, v);
     }
}