-
Notifications
You must be signed in to change notification settings - Fork 0
/
Detect a cycle in Graph using BFS.cpp
36 lines (34 loc) · 1.22 KB
/
Detect a cycle in Graph using BFS.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
class Solution {
public:
// Function to detect cycle in an undirected graph.
bool isCycle(int V, vector < int > adj[]) {
// Code here
bool visited[V] = {
0
};
for (int i = 0; i < V; i++) {
if (!visited[i]) {
queue < pair < int, int >> q;
q.push(make_pair(i, -1));
visited[i] = true;
while (!q.empty()) {
int size = q.size();
while (size--) {
pair < int, int > temp = q.front();
q.pop();
for (auto it: adj[temp.first]) {
if (!visited[it]) {
q.push(make_pair(it, temp.first));
visited[it] = true;
continue;
}
if (it != temp.second)
return true;
}
}
}
}
}
return false;
}
};