- BFS: O(V+E)
- Dijkstra[Using Priority Queue(Best)]: O((V+E)logV)
- Dijkstra[Using set(when update is required)]: O((V+E)logV)
- Bellman-Ford: O(VE)
- Floyd-Warshall: O(N^3)
- Topological sort[Using BFS]
- Topological sort[Using DFS]
- Questions:
- city and flood
- city and campers
- city and fireman vincent
- city and soldiers
- city and campers 2
- colourful array Nice problem🔥🔥🤯🤯
- Remove Max Number of Edges to Keep Graph Fully Traversable
- Khan's Algorithm[BFS for topological sort]: It only works for Directed Graph.
- Union-Find Method: Uses the Union-Find data structure to detect cycles during the union operation. It only works for an Un-Directed Graph
- DFS Method: Uses depth-first search to detect back edges. It works for both.
- Sort the nodes on the basis of finishing time of dfs.
- Reverese the edges
- Run the dfs on nodes in their sorted finishing time.
- Code