15,798,825 members
See more:
I have to build a function that returns an integer which is the number of
connected components in the graph.

What I have tried:

```I've implemented code to create the graph when adding edges or vertices.

using namespace std;

nbrs[v];
}

void Digraph::addEdge(int u, int v) {
nbrs[u].insert(v);
}

bool Digraph::isVertex(int v) {
return nbrs.find(v) != nbrs.end();
}

bool Digraph::isEdge(int u, int v) {
return nbrs.find(u) != nbrs.end() && nbrs[u].find(v) != nbrs[u].end();
}

unordered_set<int>::const_iterator Digraph::neighbours(int v) const {
return nbrs.find(v)->second.begin();
}

unordered_set<int>::const_iterator Digraph::endIterator(int v) const {
return nbrs.find(v)->second.end();
}

int Digraph::numNeighbours(int v) {
return nbrs.find(v)->second.size();
}

int Digraph::size() {
return nbrs.size();
}

vector<int> Digraph::vertices() {
vector<int> v;
for (unordered_map<int, unordered_set<int>>::const_iterator it = nbrs.begin();
it != nbrs.end(); it++) {
v.push_back(it->first);
}
return v;
}

bool Digraph::isWalk(vector<int> walk) {
if (walk.size() == 0)
return false;
if (walk.size() == 1)
return isVertex(walk[0]);
for (vector<int>::size_type i=0; i<walk.size()-1; i++)
if (!isEdge(walk[i], walk[i+1]))
return false;

return true;
}

bool Digraph::isPath(vector<int> path) {
set<int> s(path.begin(), path.end());
if (s.size() < path.size())
return false;

return isWalk(path);
}
I've started implementing code to find the connected components. I've decided to use DFS(depth first search for my solution). I'm able to implement this alone using list but I can't figure out how to implement it using an instance of this digraph class. So, far I've done this:

#include "digraph.h"
#include <iostream>
#include <vector>

using namespace std;

int count_components(Digraph& graph){

bool* visited = new bool[V];

// To store the number of connected components
int count = 0;
for (int v = 0; v < V; v++)
visited[v] = false;

for (int v = 0; v < V; v++) {
if (visited[v] == false) {
DFSUtil(v, visited);
count += 1;
}
}

return count;

}

void depthFirstSearch(const Digraph& graph, int v, int parent, unordered_map<int, int>& searchTree) {
if (searchTree.find(v) != searchTree.end()) {
return; // already visited this node
}

searchTree[v] = parent;

for (auto iter = graph.neighbours(v); iter != graph.endIterator(v); iter++) {

depthFirstSearch(graph, *iter, v, searchTree); // recursive call
}
}
//   if (!visited[*i])
// 	DFSUtil(*i, visited);
How do I implement my code to work with my graph class?
sample main driver code:

Digraph graph;
int nodes[] = {1, 2, 3, 4, 5, 6};
for (auto v : nodes)

cout << count_components(graph) << endl;
Output should be 3 in this case.```
Posted
Updated 19-Mar-21 3:36am
Rick York 15-Mar-21 23:19pm

## Solution 1

By connected components, I assume you mean the number of disjoint subgraphs. If so, I would use an edge deletion algorithm. Put each vertex in a separate set and then iterate over the edges. For each edge, combine the two sets that contain the two vertices in the edge, and then delete the edge. When no edges remain, the number of non-empty sets is the number of disjoint subgraphs.

v2