-
Notifications
You must be signed in to change notification settings - Fork 9
/
Cycle Detection In Directed Graph.cpp
106 lines (84 loc) · 2.89 KB
/
Cycle Detection In Directed Graph.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
// PROBLEM :- https://www.codingninjas.com/codestudio/problems/1062626?topList=striver-sde-sheet-problems&utm_source=striver&utm_medium=website&leftPanelTab=0
// CODE STUDIO | MEDIUM | GRAPH, CYCLES
// Solution 1 :- Using DFS -> T.C. O(V + E) S.C. O(V)
// For detection of cycle in a directed graph using DFS, we use Node Colouring technique.
// Node Color 0 -> Not visited node
// Node Color 1 -> DFS was started but still not over
// Node Color 2 -> DFS was started and also exited
// So when we are in some node, and we found its child node to be of color 1, then we conclude, CYCLE EXIST.
bool dfsCycleCheck(int node, vector<int> &nodeColor, vector<vector<int>> &adj){
nodeColor[node] = 1;
for(int i = 0 ; i < adj[node].size() ; i++){
int child = adj[node][i];
if(nodeColor[child] == 1){
return true;
}
if(nodeColor[child] == 0){
if(dfsCycleCheck(child, nodeColor, adj)){
return true;
}
}
}
nodeColor[node] = 2;
return false;
}
int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) {
vector<vector<int>> adj(n);
for(int i = 0 ; i < edges.size() ; i++){
int u = edges[i].first;
int v = edges[i].second;
u--;
v--;
adj[u].push_back(v);
}
vector<int> nodeColor(n, 0);
for(int i = 0 ; i < n ; i++){
if(nodeColor[i] == 0){
if(dfsCycleCheck(i, nodeColor, adj)){
return true;
}
}
}
return false;
}
// Solution 2 :- Using BFS -> T.C. O(V + E) S.C. O(V)
// For detection of cycle in a directed graph using BFS, we use Kahn Algo technique.
// Kahn Algo gives us Topological Sort, and if we are able to get the topo sort order, then we can conclude, cycle is not there.
// Else cycle is present.
int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) {
vector<vector<int>> adj(n);
vector<int> indegree(n, 0);
for(int i = 0 ; i < edges.size() ; i++){
int u = edges[i].first;
int v = edges[i].second;
u--;
v--;
adj[u].push_back(v);
indegree[v]++;
}
int nodesFoundInTopoSortOrder = 0;
queue<int> indegreeZero;
for(int i = 0 ; i < n ; i++){
if(indegree[i] == 0){
indegreeZero.push(i);
nodesFoundInTopoSortOrder++;
}
}
while(!indegreeZero.empty()){
int node = indegreeZero.front();
indegreeZero.pop();
for(int i = 0 ; i < adj[node].size() ; i++){
int child = adj[node][i];
indegree[child]--;
if(indegree[child] == 0){
indegreeZero.push(child);
nodesFoundInTopoSortOrder++;
}
}
}
if(nodesFoundInTopoSortOrder == n){
return false;
}else{
return true;
}
}