Number of Connected Components in an Undirected Graph 🧠

LeetCode Link: Number of Connected Components in an Undirected Graph

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 323 - Number of Connected Components in an Undirected Graph

Description: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Intuition: This problem can be approached as a graph problem where the nodes represent the vertices and the edges represent the connections between the vertices. We can use depth-first search (DFS) or breadth-first search (BFS) to explore the graph and count the number of connected components.

Approach:

1. Build an adjacency list representation of the graph using the given edges.
2. Initialize a visited array to track the visited nodes during the graph traversal.
3. Initialize a count variable to keep track of the number of connected components.
4. Iterate through each node in the graph:

• If the node is not visited, perform a DFS or BFS traversal from that node:
• Increment the count by 1.
• Mark all the connected nodes as visited.

5. Return the count, which represents the number of connected components.

⌛ Time Complexity: The time complexity depends on the graph traversal algorithm used. Using DFS or BFS, the time complexity is O(V + E), where V is the number of nodes (vertices) and E is the number of edges. We visit each node and edge once.

💾 Space Complexity: The space complexity is O(V + E), where V is the number of nodes (vertices) and E is the number of edges. This is the space used for the adjacency list and the visited array.

Solutions 💡

Cpp 💻

class Solution {
  public:
    int countComponents(int n, vector<vector<int>> &edges) {
        vector<vector<int>> graph(n);   // Adjacency list representation of the graph
        vector<int> visited(n, 0);      // Visited array to track the visited nodes
        int count = 0;                  // Number of connected components

        // Build the graph
        for (const auto &edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            graph[node1].push_back(node2);
            graph[node2].push_back(node1);
        }

        // Perform graph traversal to count the connected components
        for (int i = 0; i < n; ++i) {
            if (visited[i] == 0) {
                ++count;
                dfs(i, graph, visited);
                // Or use bfs(i, graph, visited) for BFS traversal
            }
        }

        return count;
    }

  private:
    void dfs(int node, vector<vector<int>> &graph, vector<int> &visited) {
        visited[node] = 1;  // Mark the current node as visited

        // Perform DFS traversal on the neighbors
        for (int neighbor : graph[node]) {
            if (visited[neighbor] == 0) {
                dfs(neighbor, graph, visited);
            }
        }
    }
};

Python 🐍

from collections import defaultdict, deque


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        visited = set()
        components = 0

        for node in range(n):
            if node not in visited:
                components += 1
                dfs(node)

        return components