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

Revision en1, by Dg10, 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 English Dg10 2020-09-24 21:20:22 1314 Initial revision (published)