Problem: Input: a non-directed graph G Output: a list of list of nodes representing the connected components of G (each inner list is a connected component) ConnectedComponents(G) res = CreateEmptyList() for each v in Vertices(G) if not(marked(v)) then l = CreateEmptyList() VisitComponent(G,v,l) res.push(l) return res VisitComponet(G,v,l) l.push(v) mark(v) for each w in AdjSet(v) if not(marked(w)) then VisitComponent(G,w,l) Code practically identical to DFS, but for print than becomes l.push() (which is O(1)) Thus, same complexity as DFS, i.e. O(#E + #V) in case of adjacency lists/sets.