Блог пользователя divyanshg10

Автор divyanshg10, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Why did you initialised maxlencyclepossible as vert + 10 ? ``

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -20 Проголосовать: не нравится

UPD: Sorry I misunderstood. Check the below comment.

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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).

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 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.