Good morning! Here's our prompt for today.
Can you detect a cycle in an undirected graph? Recall that an undirected graph
is one where the edges are bidirectional. A cycle is one where there is a closed path, that is, the first and last graph
vertices can be the same.

We've covered how to detect a cycle using depth-first search, but can you find one without it? Assume the following graph
definition:
JAVASCRIPT
1class Graph {
2 constructor() {
3 this.adjacencyList = new Map();
4 }
5
6 addVertex(nodeVal) {
7 this.adjacencyList.set(nodeVal, []);
8 }
9
10 addEdge(src, dest) {
11 this.adjacencyList.get(src).push(dest);
12 this.adjacencyList.get(dest).push(src);
13 }
14
15 removeVertex(val) {
16 if (this.adjacencyList.get(val)) {
17 this.adjacencyList.delete(val);
18 }
19
20 this.adjacencyList.forEach((vertex) => {
21 const neighborIdx = vertex.indexOf(val);
22 if (neighborIdx >= 0) {
23 vertex.splice(neighborIdx, 1);
24 }
25 });
26 }
27
28 removeEdge(src, dest) {
29 const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
30 this.adjacencyList.get(src).splice(srcDestIdx, 1);
31
32 const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
33 this.adjacencyList.get(dest).splice(destSrcIdx, 1);
34 }
35}
Constraints
- The number of vertices in the graph <=
100000
- The number of edges in the graph <=
100000
- Let
|V|
,|E|
represent the number of vertices and edges of the graph - Expected time complexity :
O(|V|+|E|)
- Expected space complexity :
O(|V|)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
135
const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
var assert = require('assert');
​
class UnionFind {
constructor(n) {
// fill in this method
}
​
hasCycle(adjacencyList) {
// fill in this method
}
​
union(i, j) {
// fill in this method
}
​
find(i) {
// fill in this method
}
}
​
class Graph {
constructor() {
this.adjacencyList = new Map();
this.verticesCount = 0;
}
​
addVertex(nodeVal) {
this.adjacencyList.set(nodeVal, []);
this.verticesCount++;
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?