¶ Graphs
¶ Competitive programming
¶ Introduction to Graphs in Competitive Programming
If there is one domain in competitive programming that feels like its own universe—a place with its own logic, its own language, and its own way of bending your thoughts—it is the world of graphs. The moment you step into it, you realize you’re not just dealing with numbers, or arrays, or strings anymore. You’re dealing with relationships, connections, patterns, and structures that grow and twist in ways that feel deeply mathematical yet incredibly intuitive at the same time. Graphs are everywhere, hidden in the simplest problems and powering the mightiest ones. Once you start seeing them, you can’t unsee them.
This course is an exploration of that universe, a long and steadily deepening journey into one of the richest areas of problem-solving. And it begins with a simple idea: everything can be modeled as a graph if you know what you’re looking for.
Most beginners treat graphs like an intimidating chapter they will deal with “later.” They see nodes and edges and feel a sense of heaviness. They worry about algorithms like Dijkstra, Bellman–Ford, or Tarjan, imagining them as long mechanical procedures. They hesitate at terms like strongly connected components, bridges, articulation points, topological orders, and minimum spanning trees. But the truth is far simpler: graph theory in competitive programming is not about memorizing algorithms—it’s about learning a new way to see problems.
Every time two things are connected, every time something influences something else, every time there’s a relationship between parts of a system, you already have the foundation of a graph. And once you recognize that, you start to see that graphs are not a topic—they’re a perspective.
Think of the world around you. Roads between cities? Graphs. Interactions between people? Graphs. Website links? Graphs. Dependencies in your code? Also graphs. Even the flow of logic in a problem often has a graph-like structure hiding beneath the surface. Competitive programming simply pushes you to sharpen your eyes so you notice these patterns quickly, cleanly, and confidently.
One of the turning points for many learners is realizing that graphs give shape to problems that otherwise feel shapeless. Suppose you’re given a puzzle with constraints that relate items in some strange way. Instead of struggling with raw logic, you map the items as nodes and the constraints as edges, and suddenly the structure appears. Instead of trying to reason through conditions one by one, you let the graph reveal how information flows. Representation becomes clarity, and clarity becomes speed.
Another revelation is discovering that graphs come in many flavors, each with its own personality. Some are simple, some are tricky, and some are downright mischievous. You have trees—those beautiful, acyclic creatures where everything is orderly and each pair of nodes has exactly one path between them. You have directed graphs, where direction adds an entirely new dimension of meaning. You have weighted graphs, where numbers shape paths and decisions. You have bipartite graphs, where balance creates structure. And then you have general graphs, which can be messy, unpredictable, and extremely fun to untangle.
The magic begins when you start learning how to navigate them. At first, depth-first search and breadth-first search feel like two simple techniques—just ways to visit nodes. But the more you use them, the more you realize they’re not just traversal methods—they’re perspectives. DFS gives you a sense of depth, letting you explore paths with a kind of surgical precision. BFS gives you a sense of breadth, allowing you to explore the world layer by layer. With them, you learn to measure distance, discover components, detect cycles, and uncover structure without ever needing fancy formulas.
Then you encounter shortest paths. You realize that distance is not simply a matter of counting edges—sometimes weight changes everything. You learn why Dijkstra feels intuitive once you understand how greedy exploration works. You see how Bellman–Ford handles negative weights with a kind of patient thoroughness, and you experience the beauty of Floyd–Warshall sweeping across the entire graph like a wave of insight. These algorithms stop feeling like intimidating procedures and start feeling like companions—each one suited to a particular kind of journey.
As you go deeper, graphs become even more expressive. You discover topological sorting, a technique that turns directed acyclic graphs into ordered sequences. Suddenly, problems about scheduling, dependencies, or precedence become things you can solve cleanly and confidently. You explore strongly connected components, which allow you to compress complicated loops of relationships into manageable chunks. You unravel articulation points and bridges, learning how a single connection can decide the fate of an entire network. You explore bipartiteness, matchings, flows, and cuts, where the structure of connections becomes a playground of elegant logic.
And through all this, you begin to notice something: graph problems reward imagination. They often present themselves as games, puzzles, or strange scenarios. You might be asked to move on a grid, escape from monsters, route packages, pair up students, manage resources, check for contradictions, or connect islands. But beneath the narrative lies a graph waiting to be revealed. Once you build the graph correctly, the rest of the problem starts solving itself.
Modeling becomes one of your strongest tools. The more problems you solve, the better you get at turning abstract or messy scenarios into clean graphs. A two-dimensional grid becomes a graph with weighted or unweighted connections. A string becomes a chain of states. A DP problem becomes a DAG of transitions. A puzzle with constraints becomes a graph of implications. Modeling is that subtle skill you sharpen over time, the one that separates simply solving problems from solving them intelligently.
Another underrated part of graph mastery is learning to manage memory and performance. Some graphs are tiny; some stretch to the limits of memory constraints. You might work with millions of edges or tight time limits. You learn the difference between adjacency lists and matrices. You understand the beauty of efficient edge representation and the power of compressing nodes. You learn when recursion is safe, when iterative logic is needed, when priority queues shine, and when a simple queue is king.
In contests, graph problems often sit among the medium to hard tiers, not because they are inherently difficult, but because they demand the ability to think in structures. A problem might hide a graph behind dynamic programming. Another might disguise itself as a story, only revealing its edges once you map relationships carefully. And some look like graph problems on the surface but are actually solved by seeing the right substructure—maybe a tree, maybe a cycle basis, maybe a flow network.
There is something almost artistic about realizing how the same few ideas—DFS, BFS, shortest paths, spanning trees, flow, connectivity—can combine in endlessly creative ways. You find yourself solving problems that at first seemed unrelated to graphs at all, only to discover later that everything fell into place once you represented the information as a network. This is where graph theory becomes more than a topic—it becomes a way of thinking.
As the world of competitive programming grows, graphs appear even more frequently. Not just basic ones, but multi-layered ones: state graphs, compressed graphs, implication graphs, residual networks, centroid trees, virtual trees, heavy-light decompositions. You don’t need to fear these names—each of them is just an extension of familiar ideas. What matters is the mindset you develop: the ability to break a problem into pieces and understand how those pieces connect. That skill, more than any specific technique, is what this course aims to build.
You will eventually reach the point where you look at a problem and instinctively know the shape of the graph behind it. You know when it forms a tree, when it forms components, when it forms cycles, and when it forms layers. You know whether it wants BFS, DFS, a heap, or a dynamic tree structure. You know what representation will guide you to the solution and what will bog you down. This intuition is the reward of consistent practice and deep understanding, not memorization.
And perhaps the most satisfying moment in graph problem-solving is when complexity melts away. A problem that looked impossible becomes almost trivial once its graph structure reveals itself. That feeling—the moment the fog lifts—is one of the joys of competitive programming. Graph insights don’t just solve the problem; they rewrite your understanding of it.
This introduction marks the beginning of a wide journey through paths, cycles, components, trees, cuts, flows, and countless stories that graphs help us tell. You’ll explore classic algorithms, but you’ll also learn how to adapt them, combine them, and extend them. You’ll see how the same fundamental ideas power both beginner and expert problems, and how much of success comes from representing the problem with clarity.
By the end of the course, graphs will no longer feel like a complicated topic—they’ll feel like a natural language, one you speak fluently. You’ll be able to build models easily, navigate structures intuitively, and approach even the toughest problems with confidence.
Graphs are not obstacles. They’re tools—perhaps the most expressive tools in the competitive programmer’s toolbox. Once you understand them deeply, you unlock a whole new dimension of problem-solving, one that is logical, elegant, and endlessly fascinating.
This course is your doorway into that world. Step in, explore, experiment, get lost in the patterns, and enjoy the journey. The more you travel through the landscape of graphs, the more you’ll appreciate the beauty and logic beneath every connection you draw.
¶ Graphs
¶ Beginner Concepts
1. Introduction to Graphs in Competitive Programming
2. Types of Graphs: Directed, Undirected, and Weighted
3. Basic Terminology: Nodes, Edges, and Degree
4. Graph Representation: Adjacency Matrix vs. Adjacency List
5. Understanding the Graph Data Structure
6. Simple Graph Traversal: Depth-First Search (DFS)
7. Simple Graph Traversal: Breadth-First Search (BFS)
8. Properties of Trees: A Special Case of Graphs
9. Pathfinding in Graphs: Basic Concepts and Terminology
10. Directed vs. Undirected Graphs: Key Differences
11. Degree of a Node: Understanding In-degree and Out-degree
12. Weighted Graphs and Their Applications
13. Graph Traversal with DFS: Recursive and Iterative Approaches
14. Graph Traversal with BFS: Queue-based Search
15. Connectivity in Graphs: What Does It Mean?
16. Simple Path and Cycle Detection in Graphs
17. Shortest Path Problem: Introduction and Basic Concepts
18. Topological Sort in Directed Acyclic Graphs (DAGs)
19. Pathfinding with BFS for Unweighted Graphs
20. Detecting Cycles in Directed and Undirected Graphs
21. Graph Representation Using Linked Lists
22. Graph Representation Using Arrays
23. Adjacency Matrix: Memory Considerations and Use Cases
24. Adjacency List: Space Efficiency and Performance
25. Implementing Graphs with Hashmaps
26. Understanding Eulerian and Hamiltonian Paths
27. Directed Acyclic Graphs (DAGs): Basic Properties
28. Introduction to Spanning Trees and Minimum Spanning Trees
29. Applications of Graphs in Real-World Problems
30. Introduction to Strongly Connected Components (SCCs)
31. Understanding Bipartite Graphs
32. Graph Traversal in Grid-based Problems
33. Storing Graphs Efficiently in Competitive Programming
34. Understanding the Union-Find (Disjoint Set Union) Data Structure
35. Introduction to Graph Search Complexity (Time and Space)
36. Graph Search and Component Labeling
37. Traversing Weighted Graphs: The Challenges and Methods
38. Introduction to Graph Algorithms and Their Applications
39. Pathfinding in Grid Graphs Using BFS
40. Connectivity Queries in Dynamic Graphs
¶ Intermediate Concepts
41. Dijkstra’s Algorithm for Shortest Path in Weighted Graphs
42. Bellman-Ford Algorithm for Shortest Path with Negative Weights
43. Floyd-Warshall Algorithm for All-Pairs Shortest Path
44. A* Algorithm: Advanced Pathfinding with Heuristics
45. BFS vs DFS: Understanding Their Use Cases and Differences
46. Implementing Graph Search Algorithms in C++ and Python
47. Topological Sort Algorithms: Kahn’s Algorithm and DFS-based Approach
48. Finding Strongly Connected Components (Kosaraju’s Algorithm)
49. Finding Strongly Connected Components (Tarjan’s Algorithm)
50. The Minimum Spanning Tree (MST): Introduction and Applications
51. Kruskal’s Algorithm for Minimum Spanning Tree
52. Prim’s Algorithm for Minimum Spanning Tree
53. Understanding the Cut Property in Graph Algorithms
54. Shortest Path in a Graph with Negative Weight Edges (Bellman-Ford)
55. Dijkstra’s Algorithm with Priority Queues
56. Pathfinding in Weighted Graphs with A* Search
57. Implementing Union-Find for Efficient Graph Connectivity
58. Graph Coloring and Its Applications
59. Bipartite Graph Detection using BFS or DFS
60. Finding Bridges and Articulation Points in Graphs
61. Finding Strongly Connected Components Using DFS
62. Handling Multiple Queries on Graphs Using Preprocessing
63. Applications of Dynamic Connectivity in Graphs
64. Counting the Number of Connected Components in a Graph
65. Shortest Path in an Unweighted Graph using BFS
66. Finding the Diameter of a Tree
67. Minimum Cost Path in a Graph: Introduction and Algorithms
68. Finding the Shortest Path Tree in a Graph
69. Implementing DFS Iteratively Using a Stack
70. Finding All Paths Between Two Nodes in a Graph
71. Depth First Search for Tree Traversal
72. Breadth First Search for Tree Traversal
73. Finding Connected Components in a Graph
74. Finding the Shortest Path from Multiple Sources (Multi-source BFS)
75. Finding the Shortest Path in a Grid (BFS Application)
76. Cycle Detection in Undirected Graphs with Union-Find
77. Directed Acyclic Graphs (DAGs): Applications and Algorithms
78. Introduction to Graph Search on Grid-based Problems
79. Efficiently Querying Connectivity in Graphs
80. Efficient Ways to Handle Large Graphs in Memory
¶ Advanced Concepts
81. Advanced Union-Find Techniques: Path Compression and Union by Rank
82. Euler Tour Technique for Tree Algorithms
83. Boruvka’s Algorithm for Minimum Spanning Tree
84. Finding the Shortest Path Between All Pairs of Vertices (Floyd-Warshall)
85. Advanced Dynamic Programming on Graphs
86. Solving Graph Problems with Flow Algorithms
87. Edmonds-Karp Algorithm for Maximum Flow in Networks
88. Ford-Fulkerson Algorithm for Maximum Flow
89. Min-Cost Max-Flow Problem: Theory and Implementation
90. Advanced Graph Coloring Problems: Chromatic Number
91. Understanding the Art of Graph Partitioning
92. Advanced Graph Search for Large-scale Networks
93. Network Flow Algorithms: Applications and Optimization
94. Minimum Cut and Maximum Flow Theorems
95. Understanding the Push-Relabel Algorithm for Max Flow
96. Applications of Graph Algorithms in Web Search and Ranking
97. Solving Game Theory Problems Using Graphs
98. Solving Traveling Salesman Problem (TSP) Using Graph Techniques
99. Efficiently Implementing Graph Algorithms in Large-Scale Problems
100. Implementing Graph Algorithms in Multi-threaded Environments