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 (!

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.

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 (!

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 (!

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.

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 (!

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 (!