### divyanshg10's blog

By divyanshg10, history, 5 weeks ago,

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;
}

• -40

 » 5 weeks ago, # |   +11 Why did you initialised maxlencyclepossible as vert + 10 ? 
 » 5 weeks ago, # | ← Rev. 3 →   -20 UPD: Sorry I misunderstood. Check the below comment.
•  » » 5 weeks ago, # ^ |   0 For undirected graphs, you can use DSU
 » 5 weeks ago, # | ← Rev. 2 →   +9 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.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 "$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.
•  » » » » 5 weeks ago, # ^ |   0 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).
•  » » » » » 5 weeks ago, # ^ |   0 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.