Graph Theory37 sections · 1633 units
Open in Course

Adding Directed Edges

Code Snippet

If the problem says "There is a directed edge from uu to vv" (written uvu \to v), you only update uu's list.

adj[u].push_back(v)

You do not touch vv's list because the edge only goes one way. Think of it like a one-way street: if you can drive from A to B, that does not mean you can drive from B to A.

Forgetting this asymmetry causes subtle bugs. If you accidentally add edges in both directions when the graph is directed, your BFS or DFS will explore paths that do not exist in the original problem. The algorithm finishes without errors, but returns the wrong answer.