Here is the interview question prompt, presented for reference.

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

You can see the full challenge with visuals at this link.