Topological sort, cycle detection, connected and strongly connected components

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• An edge to a grey vertex is a? from Lesson 6.1.2
• A DAG is? from Lesson 0.2.3
• BFS cost with adjacency lists? from Lesson 6.1.1

1 · The Hook

🎣

Courses have prerequisites, build steps depend on each other, spreadsheet cells refer to other cells. Any of these can be scheduled only if there is no cycle, and then a topological order lists the tasks so every dependency comes first. GATE asks how many such orders exist, and how many components a graph has.

2 · Predict First

🤔

Courses a → b means "a before b". Edges: a → b, a → c, b → d, c → d, c → e, d → f, e → f. Write one valid order of all six courses.

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

For example a, b, c, d, e, f: every arrow goes left to right. (a, c, e, b, d, f also works.)

Topological sort (only for DAGs)

A linear order with every edge u → v having u before v.

• DFS method: run DFS; output vertices in decreasing finish time. (If DFS finds a back edge, there is a cycle and no order exists.)
• Kahn's method: repeatedly output a vertex of in-degree 0 and delete its out-edges. If vertices remain but none has in-degree 0, there is a cycle.
• Both run in Θ(V + E).

For the predict DAG: Kahn (alphabetical among ready vertices) gives a, b, c, d, e, f. DFS finish times are a 12, c 11, e 10, b 7, d 6, f 5, so the DFS order is a, c, e, b, d, f. The DAG has 5 topological orders in all.

Cycle detection

• Directed: DFS back edge (grey vertex) or Kahn stalls.
• Undirected: DFS meets an already-visited vertex that is not the parent.

Connected components (undirected)

Start a BFS or DFS from every unvisited vertex; each start is a new component. Θ(V + E). A forest with V vertices and E edges has V − E components.

Strongly connected components (directed)

Maximal sets in which every vertex reaches every other. Kosaraju: DFS to get finish times; reverse every edge; DFS again in decreasing finish order; each tree of the second pass is one SCC. Θ(V + E). Collapsing each SCC to a point leaves a DAG.

4 · Visual

A DAG with DFS d/f times. Decreasing finish time gives a, c, e, b, d, f; Kahn's method gives a, b, c, d, e, f.

5 · Worked Examples

Example 1 Easy

DAG p → q, p → r, q → s, r → s. How many topological orders?

Solution

p first, s last, q and r in either order: 2.

Example 2 Medium

Directed graph: a → b, b → c, c → a, b → d, d → e, e → f, f → d, g → f, g → h, h → g. Number of strongly connected components?

Solution

{a, b, c}, {d, e, f}, {g, h}: 3.

Example 3 GATE

An undirected acyclic graph has 12 vertices and 8 edges. How many connected components?

Solution

A forest has V − E components: 4.

6 · GATE Traps

⚠️

• Topological order exists only for DAGs; there can be many.
• DFS method: decreasing finish time (not discovery time).
• SCCs need the reversed graph in Kosaraju's second pass.
• V − E components holds only for forests (no cycles).

7 · Memory Hook

🧠

"Last to finish goes first."

8 · Connect the Dots

Chapter 6.1 is complete: BFS, DFS and what they compute. Chapter 6.2 adds weights and asks for the cheapest set of edges that connects everything: the minimum spanning tree.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksTopological orders

How many topological orders does the lesson's six-course DAG have?

Numerical answer: ________

Q2NAT1 markTopological orders

A DAG on 4 vertices has edges a → b and c → d only. How many topological orders?

Numerical answer: ________

Q3MCQ1 markDFS topological sort

Using DFS, a topological order lists the vertices by:

• (A) increasing finish time
• (B) increasing discovery time
• (C) decreasing discovery time
• (D) decreasing finish time

Q4NAT1 markComponents

An undirected forest has 20 vertices and 14 edges. Number of connected components?

Numerical answer: ________

Q5NAT2 marksSCCs

Directed graph on 1–6: 1 → 2, 2 → 3, 3 → 1, 3 → 4, 4 → 5, 5 → 6, 6 → 5. Number of strongly connected components?

Numerical answer: ________

10 · Rule Card

• Topological order (DAG only): decreasing finish time, or Kahn (in-degree 0); Θ(V + E).
• Cycle: back edge (directed), visited non-parent (undirected), Kahn stalls.
• Components: one BFS/DFS start per component; forest has V − E.
• SCCs (Kosaraju): DFS, reverse edges, DFS by decreasing finish; condensation is a DAG.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

topological sortDFS-based topological orderKahn's algorithmcycle detectionconnected componentsforest V − E componentsstrongly connected componentsKosaraju's algorithmcondensation DAG

12 · Answer Vault