Graph-Coding-Minutes

Welcome to the Graph-Coding-Minutes repository! This repository contains problems taken from the course "Graph Theory Algorithms for Competitive Programming" by Prateek Narang (Coding Minutes). Each problem comes with its corresponding solution in the form of code files (As I submitted it in course) and question statements provided as PNG files. Additionally, if there are similar or exact problems available online, their links are provided in the que-link.txt file.

Table of Contents

• Roadmap
• Next Steps

Roadmap

If you're looking to follow this repository and maximize your learning, consider covering the following topics:

1. Section 3: Graph Representation

   • Adjacency List Representation
   • Adjacency Matrix Representation

2. Section 4: Breadth First Search

   • BFS on Adjacency List
   • BFS with Level Order Traversal
   • BFS on Adjacency Matrix

3. Section 5: Depth First Search

   • DFS on Adjacency List
   • DFS on Adjacency Matrix
   • DFS returning bool/int values

4. Section 6: Cycle Detection

   • Cycle Detection in Undirected Graph
   • Cycle Detection in Directed Graph
   • Bipartite Graph

5. Section 7: Directed Acyclic Graph

   • Topological Ordering/Sorting
   • Topo using DFS
   • Topo using BFS
   • When to use DFS and when to use BFS

6. Section 8: Disjoint Set Union

   • Simple DSU (union & find operations)
   • Union by Rank and Path Compression
   • Binary Search on answer (for 28-special-paths)

7. Section 9: Minimum Spanning Trees

   • Prim's Algo
   • Kruskal's Algo
   • When to use Prim and when Kruskal

8. Section 10: Shortest Path Algorithms

   • Dijkstra's Algo
   • Bellman Ford Algo
   • Floydd Warshall

9. Section 11: Travelling Salesman Problem

   • Brute Force TSP
   • TSP with DP + Bitmasking

10. Section 12: Flood Fill

    • DFS on Matrix (4-components and 8-components)

Next Steps

Once you've solved the problems for a section or a set of sections, you can further enhance your skills by:

• to improve your understanding of problems, like how to identify what concept you need to use or if it is a graph problem. Competitive programming is the best thing, so start with Codeforces problems from rating 1400 and add filters by tags. My recommendation to visit ACDLadders and solve selected problems from ACodeDaily community.
• To grind Codeforces D problems visit AskSenior and solve relevent problems.
• Contributing more resources like Editorial links, Blogs etc. for this Repository.
• For CSES problem solutions, I already have a repository. You can check it out, and for better solutions or problems not solved by me, you can refer to Abhishek Saini's Repository.

Happy Coding! 🚀 PS: If this repository was helpful to you, please give it a star. XD