Detect An Undirected Graph Cycle

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:

class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(nodeVal) {
        this.adjacencyList.set(nodeVal, []);
    }

    addEdge(src, dest) {
        this.adjacencyList.get(src).push(dest);
        this.adjacencyList.get(dest).push(src);
    }

    removeVertex(val) {
        if (this.adjacencyList.get(val)) {
            this.adjacencyList.delete(val);
        }

        this.adjacencyList.forEach((vertex) => {
            const neighborIdx = vertex.indexOf(val);
            if (neighborIdx >= 0) {
                vertex.splice(neighborIdx, 1);
            }
        });
    }

    removeEdge(src, dest) {
        const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
        this.adjacencyList.get(src).splice(srcDestIdx, 1);

        const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
        this.adjacencyList.get(dest).splice(destSrcIdx, 1);
    }
}

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|)

```js
class UnionFind {
	constructor(n) {
    // fill in this method
  }
  
  hasCycle(graph) {
    // fill in this method
  }

	union(i, j) {
    // fill in this method
	}

	find(i) {
    // fill in this method
	}
}

class Graph {
	constructor() {
		this.adjacencyList = new Map();
	}

	addVertex(nodeVal) {
		this.adjacencyList.set(nodeVal, []);
	}

	addEdge(src, dest) {
		this.adjacencyList.get(src).push(dest);
		this.adjacencyList.get(dest).push(src);
	}

	removeVertex(val) {
		if (this.adjacencyList.get(val)) {
			this.adjacencyList.delete(val);
		}

		this.adjacencyList.forEach((vertex) => {
			const neighborIdx = vertex.indexOf(val);
			if (neighborIdx >= 0) {
				vertex.splice(neighborIdx, 1);
			}
		});
	}

	removeEdge(src, dest) {
		const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
		this.adjacencyList.get(src).splice(srcDestIdx, 1);

		const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
		this.adjacencyList.get(dest).splice(destSrcIdx, 1);
  }
}
```