Graph Series: Connected components in the Undirected Graph

KuldipMochi

Follow

Oct 26, 2024

--

Listen

Share

  void traverseConnectedComponents(int source, vector<int>& visited, vector<vector<int>> adjList, vector<int>& component){
        visited[source] = 1;
        component.push_back(source);
        for(int child: adjList[source]){
            if(visited[child]==0){
                traverseConnectedComponents(child, visited, adjList, component);
            }
        }
    }
    vector<vector<int>> connectedcomponents(int v, vector<vector<int>>& edges) {
        vector<vector<int>> adjList(v);
        for(int i=0;i<edges.size();i++){
            int node1 = edges[i][0];
            int node2 = edges[i][1];
            adjList[node1].push_back(node2);
            adjList[node2].push_back(node1);
        }
        vector<vector<int>> ans;
        vector<int> visitedNodes(v, 0);
        for(int source=0;source<v;source++){
            if(visitedNodes[source]==0){
                vector<int> component;
                traverseConnectedComponents(source, visitedNodes, edges, component);
                sort(component.begin(), component.end()); //if not needed in order wise we can remove this
                ans.push_back(component);
            }
        }
        return ans;
    }