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;
}
Why did you initialised maxlencyclepossible as vert + 10 ?``UPD: Sorry I misunderstood. Check the below comment.
For undirected graphs, you can use DSU
I don't think it's correct. I doubt if you have even tested your code thoroughly. Let's say we have these edges, $$$1$$$->$$$2$$$, $$$2$$$->$$$3$$$, $$$1$$$->$$$3$$$, $$$3$$$->$$$4$$$, Your dfs function will visit $$$3$$$ in two ways $$$(1-3)$$$, and $$$(1-2-3)$$$, it will count node 3 twice, but there are no cycles obviously. You are trying to get rid of this problem by doing $$$maxlencyclepossible = vert + 10$$$, which is very skeptical, for large graphs a lot of such duplicates will be visited and the code will fail.
I think this problem can be solved by passing tillvisitednode in the dfs function (pass by value). In that way tillvisitednode > maxlencyclepossible is only possible in case of cycle.(dfs would keep on calling itself round and round) and for other cases it won't.
Please correct me if I am wrong.
"$$$tillvisitednode > maxlencyclepossible$$$ is only possible in case of cycle" — this is not true in case of $$$directed$$$ graphs. As you can see from my previous example just because you are visiting $$$3$$$ twice does not imply there is a cycle. And first of all what do you even mean by $$$maxlencyclepossible$$$? If there are $$$n$$$ nodes, maximum length of cycle is $$$n$$$, but $$$tillvisitednode > n$$$ does not mean you have a cycle in a directed graph. What you are assuming is if the number of visited nodes is sufficiently huge than we can conclude there exists a cycle and the $$$dfs()$$$ is stuck in an infinite loop and hence the huge value. But how will you determine this "sufficiently large value"? Just because you visit a particular node more than once does not mean a cycle, so different configuration of graphs will have different number of these duplicate visits, so we don't have any particular value for which we can conclude that there exists a cycle.
Just for an example take this graph : 1->2, 1->4, 1->3, 2->3, 4->3 3->{S}, here S is the set of nodes we can visit from 3. As you can see there are 3 paths from 1 -> 3, $$$(1-3)$$$, $$$(1-2-3)$$$, $$$(1-4-3)$$$, for each of these paths, all nodes in S will be visited again. And we have the choice to create more paths from 1->3. On top of that we are assuming that there is no such complexity in the set S and they will be visited once, but life is not so simple always.
I think you did not see the part where I said, we send tillvisitednode as pass by value and not reference. Meaning for every path as you mentioned from 1, it will have count corresponding to that path.
For example, if I go (1->3) value at that time will be 2, while if I go (1->2->3) value will be 3 and similarly 3 for the path(1->4->3). So you see unless I go round and round I may never be able to increase it infinitely.
I am not saying that the above algorithm is definitely correct. But I just want an example where it will definitely fail(after the modification which I suggested in the previous comment).
Yeah unfortunately I missed that part pass by value. In that case what we are simply doing is traversing through all possible paths in the graph, and if any path contains more than n nodes then there is definitely a cycle and this should work. The only problem is time complexity will be huge and it will only work for very small graph.