Good afternoon! 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?
xxxxxxxxxx135
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?