Order a set of tasks so each task comes after the things it depends on. The same code also tells you when no order exists.
“X must happen before Y” describes a directed graph. The question is almost always one of two. Give me a valid order. Or is a valid order even possible? About twenty lines of C# answer both. The second answer falls out of the first for free.
PriorityQueue<int, int>. Everything else stays the same.Reading the figure. Each arrow points from a prerequisite to the node it unlocks. The small grey label is the starting in-degree. Nodes 0 and 1 start at zero, so they go first (green). Each colour after that is one more round of nodes whose count just hit zero.
[a, b] means “to take a, first take b”. That is an edge from b to a. It raises the in-degree of a. Reversing this is the most common way to fail these problems. The reversed code still gives a plausible answer on symmetric tests. Read the statement twice. Write one example edge on the board.order.Count == n is a full cycle test. It costs one comparison.So “can you finish all courses” and “give me the order” are the same method. Only the return statement differs.
StackOverflowException, which you cannot catch.C# has no built-in deque. Kahn only needs a plain FIFO, so Queue<T> is the right tool. Edges are passed as named tuples (int Before, int After)[]. A test can then write [(0, 1), (1, 2)] as a collection expression.
public static class TopoKahn
{
/// <summary>Orders nodes 0..n-1 so every edge (Before, After) is respected.</summary>
/// <param name="n">Number of nodes, labelled 0 to n - 1.</param>
/// <param name="edges">Pairs where Before must come ahead of After.</param>
/// <returns>A valid order, or an empty list if the graph has a cycle.</returns>
/// <example>TopologicalOrder(3, [(0, 1), (1, 2)]) returns [0, 1, 2].</example>
public static List<int> TopologicalOrder(int n, (int Before, int After)[] edges)
{
// One empty successor list per node. i runs over labels 0..n-1.
var successors = new List<int>[n];
for (int i = 0; i < n; i++) successors[i] = [];
// indegree[node] = prerequisites not placed yet. new int[n] starts every count at 0.
var indegree = new int[n];
foreach (var (before, after) in edges)
{
successors[before].Add(after);
indegree[after]++; // +1: after waits on one more node
}
// Seed with every node at indegree 0: nothing blocks them.
var queue = new Queue<int>();
for (int node = 0; node < n; node++) // node: label being tested, 0..n-1
if (indegree[node] == 0) queue.Enqueue(node);
var order = new List<int>(n); // n: the final size when there is no cycle
// Invariant: every node in order, or in the queue, has all its
// prerequisites already placed in order.
while (queue.Count > 0) // 0: an empty queue means nothing is ready
{
int node = queue.Dequeue();
order.Add(node);
// Placing node clears one prerequisite for each successor.
foreach (int next in successors[node])
{
indegree[next]--; // -1: one fewer prerequisite left
if (indegree[next] == 0) // 0: its last prerequisite just cleared
queue.Enqueue(next);
}
}
// Fewer than n placed means some nodes never reached 0: a cycle.
return order.Count == n ? order : [];
}
}Decrement, then test, in that order. Test for exactly zero. Testing <= 0 would enqueue a node twice on a multi-edge.
/// <summary>Node states for the DFS template.</summary>
public enum Colour
{
White, // 0, the default: not visited yet
Grey, // on the current DFS path
Black, // finished, all descendants done
}
public static class TopoDfs
{
/// <summary>Same result as Kahn, using post-order DFS. Grey means a cycle.</summary>
/// <param name="n">Number of nodes, labelled 0 to n - 1.</param>
/// <param name="edges">Pairs where Before must come ahead of After.</param>
/// <returns>A valid order, or an empty list if the graph has a cycle.</returns>
/// <example>TopologicalOrderDfs(3, [(0, 1), (1, 2)]) returns [0, 1, 2].</example>
public static List<int> TopologicalOrderDfs(int n, (int Before, int After)[] edges)
{
// One empty successor list per node. i runs over labels 0..n-1.
var successors = new List<int>[n];
for (int i = 0; i < n; i++) successors[i] = [];
foreach (var (before, after) in edges) successors[before].Add(after);
// new Colour[n] fills with White, the enum's 0 value: every node unvisited.
var colour = new Colour[n];
var order = new List<int>(n); // n: the final size when there is no cycle
// Returns false if a cycle is reachable from node, else true.
bool Visit(int node)
{
if (colour[node] == Colour.Grey) return false; // back edge: a cycle
if (colour[node] == Colour.Black) return true; // already finished
colour[node] = Colour.Grey; // node is now on the current path
foreach (int next in successors[node])
if (!Visit(next)) return false; // pass the cycle signal up
colour[node] = Colour.Black; // all descendants done, leave the path
order.Add(node); // post-order: after all descendants
return true;
}
// Start a DFS from every node so disconnected parts are covered.
for (int node = 0; node < n; node++) // node: label 0..n-1
if (!Visit(node)) return []; // empty list: a cycle, no valid order
order.Reverse(); // post-order is the reverse topo order
return order;
}
}Grey means “on the current path”. Reaching a grey node means the path loops back on itself. Black means “done, and safe to skip”. Two colours are not enough. They cannot tell those two cases apart. A local function keeps colour and order in scope without extra parameters.
Reading the figure. Amber nodes are grey, which means they are on the current DFS path. Green is black, meaning the node and all its descendants are done. Neutral is white, not visited yet. On the left, node 2 finishes first, so post-order lists it first. On the right, the red edge from 2 points at a grey node. That back edge is the cycle signal.
public static class TopoSmallest
{
/// <summary>Kahn's algorithm with a min-heap instead of a FIFO queue.</summary>
/// <param name="n">Number of nodes, labelled 0 to n - 1.</param>
/// <param name="edges">Pairs where Before must come ahead of After.</param>
/// <returns>The smallest valid order, or an empty list on a cycle.</returns>
/// <example>SmallestTopologicalOrder(4, [(0, 3), (1, 2)]) returns [0, 1, 2, 3].</example>
public static List<int> SmallestTopologicalOrder(int n, (int Before, int After)[] edges)
{
// One empty successor list per node. i runs over labels 0..n-1.
var successors = new List<int>[n];
for (int i = 0; i < n; i++) successors[i] = [];
var indegree = new int[n]; // new int[n]: every count starts at 0
foreach (var (before, after) in edges)
{
successors[before].Add(after);
indegree[after]++; // +1: after waits on one more node
}
// PriorityQueue is a min-heap. The node label is also its priority.
var ready = new PriorityQueue<int, int>();
for (int node = 0; node < n; node++) // node: label being tested, 0..n-1
if (indegree[node] == 0) ready.Enqueue(node, node);
var order = new List<int>(n); // n: the final size when there is no cycle
// Invariant: ready holds exactly the unplaced nodes with no blockers left.
while (ready.Count > 0) // 0: nothing is ready
{
int node = ready.Dequeue(); // always the smallest available node
order.Add(node);
foreach (int next in successors[node])
{
indegree[next]--; // -1: one fewer prerequisite left
if (indegree[next] == 0) // 0: nothing blocks it now
ready.Enqueue(next, next);
}
}
// Fewer than n placed means a cycle blocked the rest.
return order.Count == n ? order : [];
}
}One data-structure swap turns any valid order into the smallest one. Cost rises from O(V + E) to O(V log V + E). Each node enters the heap once, so the missing decrease-key in PriorityQueue does not matter here.
Reading the figure. Both runs start with 0 and 1 ready, so the gray cells match. Then 3 and 2 become ready in that order. Queue<int> hands them out in arrival order (amber). PriorityQueue<int, int> hands out the smallest first (green). Both orders are valid. Only the heap gives the smallest one.
indegree <= 0. With duplicate edges, that enqueues a node twice. Test for exactly 0.List<T>.Reverse() flips it in place.new List<int>[n] holds n nulls. Fill each slot before you call Add.There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] means you must take course b before course a. Return true if you can finish all courses.
[a, b] is an edge from b to a. Taking b unlocks a.public static class CourseSchedule
{
/// <summary>True if every course can be taken, given the prerequisite pairs.</summary>
/// <param name="numCourses">Courses are labelled 0 to numCourses - 1.</param>
/// <param name="prerequisites">Pairs [a, b] meaning b must be taken before a.</param>
/// <returns>True if the prerequisite graph is acyclic.</returns>
/// <example>CanFinish(2, [[1, 0]]) returns true. CanFinish(2, [[1, 0], [0, 1]]) returns
/// false.</example>
public static bool CanFinish(int numCourses, int[][] prerequisites)
{
// unlocks[c] = courses that list c as a prerequisite. i runs over labels 0..n-1.
var unlocks = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) unlocks[i] = [];
var indegree = new int[numCourses]; // new int[n]: every count starts at 0
foreach (int[] pair in prerequisites)
{
// [0] is the course, [1] is the course it needs first.
int course = pair[0], needs = pair[1];
// Edge runs from the prerequisite to the course it unlocks.
unlocks[needs].Add(course);
indegree[course]++; // +1: course waits on one more
}
// Start with every course that has 0 prerequisites.
var queue = new Queue<int>();
for (int c = 0; c < numCourses; c++) // c: course label being tested
if (indegree[c] == 0) queue.Enqueue(c);
int taken = 0; // 0: no courses taken yet
// Invariant: taken counts courses whose prerequisites were all taken first.
while (queue.Count > 0) // 0: nothing is ready
{
int course = queue.Dequeue();
taken++; // +1: one more course done
foreach (int next in unlocks[course])
{
indegree[next]--; // -1: one prerequisite of next is done
if (indegree[next] == 0) // 0: next is ready to take
queue.Enqueue(next);
}
}
// Anything never emitted is stuck waiting inside a cycle.
return taken == numCourses;
}
}Take numCourses = 2 and prerequisites = [[1, 0], [0, 1]]. Course 1 needs 0, and course 0 needs 1. Both in-degrees are 1. So the first queue is empty and the loop never runs. taken stays 0. Since 0 != 2, the answer is false. No explicit cycle-finding code was needed.
Reading the figure. Each arrow points from a prerequisite to the course it unlocks. Both nodes are red because each waits on the other. Neither count can drop to 0. So the queue starts empty and the count of taken courses stays below 2.
V is numCourses and E is the number of prerequisite pairs. Every node is queued once. Every edge is relaxed once.
public static class CourseSemesters
{
/// <summary>Fewest terms to finish everything, taking any ready courses per term.</summary>
/// <param name="numCourses">Courses are labelled 0 to numCourses - 1.</param>
/// <param name="prerequisites">Pairs [a, b] meaning b must be taken before a.</param>
/// <returns>The number of semesters, or -1 if a cycle blocks some course.</returns>
/// <example>MinimumSemesters(3, [[1, 0], [2, 1]]) returns 3.</example>
public static int MinimumSemesters(int numCourses, int[][] prerequisites)
{
// unlocks[c] = courses that list c as a prerequisite. i runs over labels 0..n-1.
var unlocks = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) unlocks[i] = [];
var indegree = new int[numCourses]; // new int[n]: every count starts at 0
foreach (int[] pair in prerequisites)
{
// [0] is the course, [1] is the course it needs first.
unlocks[pair[1]].Add(pair[0]);
indegree[pair[0]]++; // +1: course waits on one more
}
// The first semester is every course with 0 prerequisites.
var queue = new Queue<int>();
for (int c = 0; c < numCourses; c++) // c: course label being tested
if (indegree[c] == 0) queue.Enqueue(c);
int taken = 0; // 0: no courses taken yet
int semesters = 0; // 0: no terms used yet
// Invariant: at the top of each pass, the queue holds exactly the
// courses that can be taken this semester.
while (queue.Count > 0) // 0: nothing is ready
{
// Snapshot the count first. The queue grows while we drain it.
int size = queue.Count;
for (int k = 0; k < size; k++) // k: courses taken so far this term
{
int course = queue.Dequeue();
taken++; // +1: one more course done
foreach (int next in unlocks[course])
{
indegree[next]--; // -1: one prerequisite of next is done
if (indegree[next] == 0) // 0: ready, so it joins next semester
queue.Enqueue(next);
}
}
semesters++; // +1: that semester is over
}
// -1: some courses sit in a cycle and can never be taken.
return taken == numCourses ? semesters : -1;
}
}Read queue.Count into size once, before the inner loop. Writing k < queue.Count in the loop header would re-read a growing count. It would merge semesters. This is the level-size trick from Pattern 7, unchanged. The layers of a topological sort are BFS rounds.
true.[0, 0]: in-degree 1 that nothing can clear, so false. Ask whether self-loops can appear.== 0.numCourses = 0: returns true.Same input, but return an actual order in which all courses can be taken. Return an empty list if no order exists.
List<int> and add each course as it is emitted.public static class CourseScheduleII
{
/// <summary>An order in which all courses can be taken, or empty if impossible.</summary>
/// <param name="numCourses">Courses are labelled 0 to numCourses - 1.</param>
/// <param name="prerequisites">Pairs [a, b] meaning b must be taken before a.</param>
/// <returns>A valid ordering, or an empty list when the graph has a cycle.</returns>
/// <example>FindOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) returns [0, 1, 2, 3].</example>
public static List<int> FindOrder(int numCourses, int[][] prerequisites)
{
// unlocks[c] = courses that list c as a prerequisite. i runs over labels 0..n-1.
var unlocks = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) unlocks[i] = [];
var indegree = new int[numCourses]; // new int[n]: every count starts at 0
foreach (int[] pair in prerequisites)
{
// [0] is the course, [1] is the course it needs first.
int course = pair[0], needs = pair[1];
unlocks[needs].Add(course); // edge: prerequisite -> course
indegree[course]++; // +1: course waits on one more
}
// Start with every course that has 0 prerequisites.
var queue = new Queue<int>();
for (int c = 0; c < numCourses; c++) // c: course label being tested
if (indegree[c] == 0) queue.Enqueue(c);
var order = new List<int>(numCourses); // capacity: the full size if no cycle
// Invariant: every course in order came after all its prerequisites.
while (queue.Count > 0) // 0: nothing is ready
{
int course = queue.Dequeue();
order.Add(course);
foreach (int next in unlocks[course])
{
indegree[next]--; // -1: one prerequisite of next is done
if (indegree[next] == 0) // 0: next is ready to take
queue.Enqueue(next);
}
}
// A short order means some courses never became available: a cycle.
return order.Count == numCourses ? order : [];
}
}Take numCourses = 4 and pairs [[1,0],[2,0],[3,1],[3,2]]. Course 0 unlocks 1 and 2. Both of those unlock 3.
[0, 1, 1, 2]. Queue [0].[0, 0, 0, 2]. Queue [1, 2].[0, 0, 0, 1]. Queue [2].[0, 0, 0, 0]. Queue [3].[]. The loop ends.The result is [0, 1, 2, 3]. [0, 2, 1, 3] is equally valid. Which one you get depends only on the order inside the queue.
Reading the figure. Each box is one step. Green nodes are already in the order. Amber nodes are in the queue. Gray nodes still wait on a prerequisite. The text under each graph shows the in-degree list, the queue, and the order so far. Node 3 needs two decrements. So it turns amber only after both 1 and 2 are emitted.
order, all its prerequisites are already there. Why? The course entered the queue only when its in-degree reached zero. Each decrement came from a prerequisite at the moment it was emitted. Induction on the emissions finishes the proof. Stating this in two sentences shows you understand the code, not just remember it.[0, 1, …, n-1], which is valid.[], even if most of the graph is fine.You get a list of words in an alien language. They are sorted by that language’s letter order. Recover one possible ordering of its letters. Return "" if the input is inconsistent.
Non-adjacent pairs add nothing. If a < b and b < c, then a < c follows. The topological sort handles that transitivity. So n - 1 comparisons are enough, not n². Saying that is worth a point on its own.
["abc", "ab"].
"".["a", "b", "a"].
["z", "x"] with an unseen letter.
Two C# notes. C# has no for/else, so a bool flag records whether a difference was found. And Dictionary order is not guaranteed. A separate List<char> keeps letters in first-seen order, so the output is deterministic.
using System.Text;
public static class AlienDictionary
{
/// <summary>Recovers a letter order consistent with a sorted alien word list.</summary>
/// <param name="words">Words sorted by the unknown alphabet.</param>
/// <returns>One valid order of every letter that appears, or "" if the input is
/// contradictory.</returns>
/// <example>AlienOrder(["wrt", "wrf", "er", "ett", "rftt"]) returns "wertf".</example>
public static string AlienOrder(string[] words)
{
// letter -> letters that must come after it. A HashSet blocks duplicate edges.
var successors = new Dictionary<char, HashSet<char>>();
// Every letter that appears must be in the answer, even with no edges.
var indegree = new Dictionary<char, int>();
// First-seen order, because Dictionary order is not guaranteed.
var letters = new List<char>();
foreach (string word in words)
foreach (char ch in word)
if (indegree.TryAdd(ch, 0)) // 0: no incoming edges counted yet
{
letters.Add(ch);
successors[ch] = [];
}
// i: index of the second word in each adjacent pair. Starts at 1 so i - 1 exists.
for (int i = 1; i < words.Length; i++)
{
// i - 1: the word just before words[i].
string first = words[i - 1], second = words[i];
int shared = Math.Min(first.Length, second.Length);
bool foundDifference = false;
// j: position compared. Invariant: first[..j] equals second[..j].
for (int j = 0; j < shared; j++)
{
char a = first[j], b = second[j];
if (a == b) continue;
// The first difference is the only constraint this pair gives.
if (successors[a].Add(b)) // Add returns false if the edge exists
indegree[b]++; // +1: b waits on one more letter
foundDifference = true;
break;
}
// No difference in the shared length. A longer word may not precede its prefix.
if (!foundDifference && first.Length > second.Length)
return ""; // "": the input is contradictory
}
// Start with every letter that has 0 incoming edges.
var queue = new Queue<char>();
foreach (char ch in letters)
if (indegree[ch] == 0) queue.Enqueue(ch);
var order = new StringBuilder(letters.Count); // strings are immutable: build once
// Invariant: each letter in order comes after every letter that must precede it.
while (queue.Count > 0) // 0: nothing is ready
{
char ch = queue.Dequeue();
order.Append(ch);
foreach (char next in successors[ch])
{
indegree[next]--; // -1: one blocker of next is placed
if (indegree[next] == 0) // 0: next is free to place
queue.Enqueue(next);
}
}
// Missing letters were stuck in a cycle, so return "" for no valid order.
return order.Length == letters.Count ? order.ToString() : "";
}
}Input ["wrt", "wrf", "er", "ett", "rftt"]:
t vs f. Edge t → f.w vs e. Edge w → e.r vs t. Edge r → t.e vs r. Edge e → r.The edges form one chain, w → e → r → t → f. So the order is "wertf", and it is unique here. Each pair produced exactly one edge. Everything after the first difference was ignored.
Reading the figure. Each column is one pair of adjacent words. Gray letters match. The amber letters are the first place the words differ, and they give one edge. Dashed letters come after the difference and are ignored. The green chain at the bottom is the topological sort of those four edges.
C is the total number of characters across all words. U is the alphabet size. The graph has at most U nodes and U² edges. With a fixed alphabet, the space is constant. Quote O(1) with that reason. It is the sharper answer.
indegree with every letter seen. A letter with no constraints still belongs in the output. Building the node set from the edges alone drops it.break after the first difference. Going on would make constraints the input does not support.HashSet<char>.Add returns false for a repeat. Without that check, the in-degree is inflated and never reaches zero.["abc"]: no pairs, no edges. Any order of a, b, c is valid.["abc", "ab"]: prefix rule violated, returns "".["ab", "abc"]: legal, and yields no edge.Queue<int> of ready nodes, decrement and enqueue at zero.n nodes means the rest are stuck in a cycle.PriorityQueue<int, int> to get the smallest order. Use the level-size trick to count layers.Pattern 16, Union-Find, is the other graph structure worth owning. Topological sort answers questions about direction and order. Union-Find answers questions about connectivity, on a graph that keeps changing. The Python version of this page is here.