-
Notifications
You must be signed in to change notification settings - Fork 0
/
cycle.cpp
65 lines (53 loc) · 1.44 KB
/
cycle.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
private:
int numVertices;
vector<vector<int>> adjList;
public:
Graph(int vertices) {
numVertices = vertices;
adjList.resize(numVertices);
}
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
bool isCyclicUtil(int v, vector<bool>& visited, vector<bool>& recursionStack) {
visited[v] = true;
recursionStack[v] = true;
for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
if (isCyclicUtil(neighbor, visited, recursionStack))
return true;
} else if (recursionStack[neighbor]) {
return true;
}
}
recursionStack[v] = false;
return false;
}
bool isCyclic() {
vector<bool> visited(numVertices, false);
vector<bool> recursionStack(numVertices, false);
for (int v = 0; v < numVertices; ++v) {
if (!visited[v] && isCyclicUtil(v, visited, recursionStack))
return true;
}
return false;
}
};
int main() {
Graph graph(4);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
if (graph.isCyclic()) {
cout << "Cycle detected in the graph" << endl;
} else {
cout << "No cycle detected in the graph" << endl;
}
return 0;
}