Rat in a maze

Read more →

M coloring

Read more →

Create and print a graph

Read more →

Implement BFS

https://practice.geeksforgeeks.org/problems/bfs-traversal-of-graph/1 GfG has incorrect testcases. Always check for multiple components, which requires the commented outer visited loop. class Solution { vector<int> bfsTraversal; void bfs(int i, vector<bool> &visited, vector<int> adj[]) { queue<int> q; visited[i] = true; q.push(i); while (!q.empty()) { int node = q.front(); q.pop(); bfsTraversal.push_back(node); for (int it : adj[node]) { if (!visited[it]) { visited[it] = true; q.push(it); } } } } public: vector<int> bfsOfGraph(int V, vector<int> adj[]) { vector<bool> visited(V, false); // for (int i = 0; i < V; i++) { // if (!
Read more →

Implement DFS

https://practice.geeksforgeeks.org/problems/depth-first-traversal-for-a-graph/1 Recursive class Solution { vector<int> dfsTraversal; void dfsHelper(int i, vector<bool> &visited, vector<int> adj[]) { visited[i] = true; dfsTraversal.push_back(i); for (vector<int>::iterator it = adj[i].begin(); it != adj[i].end(); it++) { if (!visited[*it]) { dfs(*it, visited, adj); } } } public: vector<int> dfsOfGraph(int V, vector<int> adj[]) { vector<bool> visited(V, false); for (int i = 0; i < V; i++) { if (!visited[i]) { dfsHelper(i, visited, adj); } } return dfsTraversal; } }; Iterative class Solution { vector<int> dfsTraversal; void dfsHelper(int i, vector<bool> &visited, vector<int> adj[]) { stack<int> st; visited[i] = true; st.
Read more →

Detect cycle in directed graph using BFS/DFS

https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ Using DFS class Solution { bool dfsHelper(int i, vector<bool> &visited, vector<bool> &visitedDirected, vector<int> adj[]) { visited[i] = true; visitedDirected[i] = true; for (int it : adj[i]) { if (!visited[it]) { if (dfsHelper(it, visited, visitedDirected, adj)) { return true; } } else if (visitedDirected[it]) { return true; } } visitedDirected[i] = false; return false; } public: bool isCyclic(int V, vector<int> adj[]) { vector<bool> visited(V, false); vector<bool> visitedDirected(V, false); for (int i = 0; i < V; i++) { if (!
Read more →

Detect cycle in undirected graph using BFS/DFS

https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1 DFS class Solution { bool dfsHelper(int i, int p, vector<bool> &visited, vector<int> adj[]) { visited[i] = true; for (auto it : adj[i]) { if (visited[it] == false) { if (dfsHelper(it, i, visited, adj)) { return true; } } else if (it != p) { return true; } } return false; } public: bool isCycle(int V, vector<int> adj[]) { vector<bool> visited(V, false); for (int i = 0; i < V; i++) { if (!
Read more →

Minimum steps by knight

https://practice.geeksforgeeks.org/problems/steps-by-knight/0 class pos { public: int x, y, dist; pos(int x, int y, int dist) : x(x), y(y), dist(dist) {} }; class Solution { bool isInside(int x, int y, int N) { return (x >= 1 and x <= N and y >= 1 and y <= N); } public: int minStepToReachTarget(vector<int> &KnightPos, vector<int> &TargetPos, int N) { vector<pair<int, int>> dir = { {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, }; bool visited[N + 1][N + 1] = {0}; queue<pos> q; q.
Read more →

Flood fill algorithm

Read more →

Clone a graph

Read more →

Making wired connections

Read more →

Word ladder

Read more →

Dijkstra algorithm

Read more →

Implement topological sort

https://practice.geeksforgeeks.org/problems/topological-sort/1 Topological sort is only valid for a Directed Acyclic Graph Using DFS class Solution { stack<int> st; void dfsHelper(int i, vector<bool> &visited, vector<int> adj[]) { visited[i] = true; for (auto it : adj[i]) { if (!visited[it]) { visited[it] = true; dfsHelper(it, visited, adj); } } st.push(i); } public: vector<int> topoSort(int V, vector<int> adj[]) { vector<bool> visited(V, false); for (int i = 0; i < V; i++) { if (!
Read more →

Minimum time taken by each job to be completed given by a directed acyclic graph

Read more →

Find whether it is possible to finish all tasks from given dependencies

Read more →

Find the number of islands

Read more →

Given a sorted dictionary of an alien language, find order of characters

Read more →

Implement Kruksal’s algorithm

Read more →

Implement Prim’s algorithm

Read more →

Total number of spanning tree in a graph

Read more →

Implement Bellman Ford algorithm

Read more →

Implement Floyd Warshall algorithm

Read more →

Travelling salesman

Read more →

Graph colouring

Read more →

Snake and ladders

Read more →

Find bridge in a graph

Read more →

Count strongly connected components (Kosaraju algorithm)

Read more →

Check if graph is bipartite

https://www.geeksforgeeks.org/bipartite-graph/ Color the graph by BFS traversal, colors maintains track of visited nodes. colors[it] = 1 - colors[node] is the fun alternator part Using BFS class Solution { bool bfsHelper(int i, vector<int> &colors, vector<int> adj[]) { queue<int> q; colors[i] = 1; q.push(i); while (!q.empty()) { int node = q.front(); q.pop(); for (int it : adj[node]) { if (colors[it] == -1) { colors[it] = 1 - colors[node]; q.push(it); } else if (colors[it] == colors[node]) { return false; } } } return true; } public: bool isBipartite(int V, vector<int> adj[]) { vector<int> colors(V, -1); for (int i = 0; i < V; i++) { if (colors[i] == -1) { if (!
Read more →

Detect negative cycle in a graph

Read more →

Longest path in a directed acyclic graph

Read more →

Journey to the moon

Read more →

Cheapest flights within K stops

Read more →

Oliver and the game

Read more →

Water jug using BFS

Read more →

Minimum edges to reverse to make path from source to destination

Read more →

Paths to travel each nodes using each edge

Read more →

Vertex cover

Read more →

Chinese postman or route inspection

Read more →

Number of triangles in a directed and undirected graph

Read more →

Minimise the cashflow in a set of friends

Read more →

Two clique

Read more →