323. Number of Connected Components in an Undirected Graph

📝 Problem Details

• Title: 323. Number of Connected Components in an Undirected Graph
• Link: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
• Difficulty: Medium
• Tags/Categories: Graphs DFS

input integer n input array edges where edges[i] = [ai, bi] return the number of connected components in the graph

💭What Were My Initial Thoughts?

- traverse the graph using DFS

💡 Explanation of Solution

- each DFS call at the top of the call stack represents a new connected component

⌛ Complexity Analysis

Time Complexity: O(V+E)
Space Complexity: O(V+E)

💻 Implementation of Solution

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        
        // construct the adjList
        vector<vector<int>> adjList(n);
 
        for(const auto& edge : edges) {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }
 
        int count = 0;
        vector<int> visited(n,0); // 0 = unvisited, 1 = visited
 
        // run dfs for detection of connected components
        for(int i=0; i < n; i++) {
            // each new DFS call represents a new connected component
            if(!visited[i]) { // found new connected component
                dfs(i, adjList, visited);
                count++;
            }
        }
        return count;
    }
 
    void dfs(int node, vector<vector<int>>& adjList, vector<int>& visited) {
        visited[node] = 1; // mark as visited
        for(int neighbour : adjList[node]) {
            if(!visited[neighbour]) {
                dfs(neighbour, adjList, visited);
            }
        }
    }
};