hii everyone, I recently found a very simple trick to detect cycle in directed graph. Hope you also find it interesting!

Revision en1, by divyanshg10, 2020-09-24 21:20:22

Simply perform a dfs and count the number of nodes visited, if the count increases number of vertices then there is definitely a cycle.

#include<bits/stdc++.h>
using namespace std;
bool vis[100005];
int maxlencyclepossible = 0, tillvisitednode = 0;
void dfs(vector<int> graph[], int node) {
if (tillvisitednode > maxlencyclepossible) {
return;
}
for (auto child : graph[node]) {
vis[node] = true;
tillvisitednode++;
dfs(graph, child);
}
return;
}
void solve() {
int vert, edge;
vert = 4, edge = 3;
memset(vis, false, sizeof(vis));
vector<int> graph[vert];
// zero based
graph[0].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
//cycle between 2 and 3
tillvisitednode = 0;
maxlencyclepossible = vert + 10;
tillvisitednode = 0;
maxlencyclepossible = vert + 10;
for (int i = 0; i < vert; i++) {
tillvisitednode = 0;
if (!vis[i]) {
dfs(graph, i);
}
if (tillvisitednode > maxlencyclepossible) {
break;
}
}
if (tillvisitednode > maxlencyclepossible) {
cout << "Cycle Detected\n";
return;
}
cout << "No Cycle Detected\n";
return ;
}
int main() {
solve();
return 0;
}

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 divyanshg10 2020-09-24 21:20:22 1314 Initial revision (published)