Given a list of edges, how many connected components can be found?

Given a list of edges such that the undirected graph generated cannot have multiple edges but can have loops. How many connected components can be found?

This is best demonstrated with an example. Given this list of edges:

A -- A
A -- B
B -- C
B -- D
B -- F
G -- H
H -- I
I -- G

There are two connected components that can be found:

Is there a way to determine how many connected components can be found without actually constructing the graph?

1 Answer

I ended up using a depth first search approach to solving this:

a) Pick a random node and mark as visited
b) Find all nodes adjacent and repeat algorithm on each
c) If no adjacent nodes are found, exit
d) Increment component counter by 1
e) Repeat algorithm if not all nodes in the list have been visited

This isn't a mathematical solution as I had hoped for, but it works.