Advanced · Module 13 · Lesson 4 of 5

Cycles and connected components

One walk over a graph can split it into connected pieces, tell whether it is a tree, and find cycles. Directed graphs need one extra idea: remembering which vertices are on the current path.

ProAbout 14 minutes

By the end you can

Count and label the connected components of an undirected graph
Detect a cycle in an undirected graph, and decide whether a graph is a tree
Detect a cycle in a directed graph with three colors, and explain why a visited set isn't enough

Builds on Depth-first search.

01 · A question first

A package manager must refuse to install packages whose dependencies loop back on themselves. A network tool must report how many separate networks are plugged together. Both come down to one walk over a graph. What does that walk need to remember?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Connected components
Cycles in undirected graphs
Cycles in directed graphs
Strongly connected components
Where this shows up
Pseudocode & Multi-Language Implementations (C++, Java, Python)
Complexity Derivation, Edge Cases & Common Mistakes

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeNumber of connected components in an undirected graphCount the connected components of a graph by starting a search from every vertex not yet visited.Practice · medium · LeetCodeSurrounded regionsCapture regions of O cells that don't touch the border, by first marking every O reachable from the border.Practice · medium · LeetCodeFind eventual safe statesFind the vertices of a directed graph from which every path ends at a terminal vertex, using three-color DFS.

Asked in interviews

How do you detect a cycle in a directed graph?

Something wrong with this lesson? Report a problem