261-Graph-Valid-Tree.js

/**
 * https://leetcode.com/problems/graph-valid-tree/
 * Time O(E * a(N)) | Space O(V)
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function(n, edges, root = 0) {
    const isEqual = edges.length === (n - 1)
    if (!isEqual) return false;

    const { graph, visited } = buildGraph(n, edges)

    dfs(root, graph, visited);

    return visited.size === n;
}

var initGraph = (n) => ({
    graph: new Array(n).fill().map(() => []),
    visited: new Set()
})

var buildGraph = (n, edges) => {
    const { graph, visited } = initGraph(n)

    for (const [ src, dst ] of edges) {
        graph[src].push(dst);
        graph[dst].push(src);
    }

    return { graph, visited }
}

const dfs = (node, graph, visited) => {
    if (visited.has(node)) return;
    visited.add(node);

    for (const neighbor of graph[node]) {
        dfs(neighbor, graph, visited);
    }
}

/**
 * https://leetcode.com/problems/graph-valid-tree/
 * Time O(E * a(N)) | Space O(V)
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function(n, edges) {
    const isEqual = edges.length === (n - 1)
    if (!isEqual) return false;

    const { graph, visited, queue } = buildGraph(n, edges)

    bfs(graph, visited, queue)

    return visited.size === n;
}

var initGraph = (n) => ({
    graph: new Array(n).fill().map(() => []),
    visited: new Set(),
    queue: new Queue(),
    root: 0
})

var buildGraph = (n, edges) => {
    const { graph, visited, queue, root } = initGraph(n)

    for (const [ src, dst ] of edges) {
        graph[src].push(dst);
        graph[dst].push(src);
    }

    queue.enqueue(root);
    visited.add(root);

    return { graph, visited, queue }
}

const bfs = (graph, visited, queue) => {
    while (!queue.isEmpty()) {
        for (let i = (queue.size() - 1); 0 <= i; i--) {
            checkNeighbor(graph, visited, queue)
        }
    }
}

const checkNeighbor = (graph, visited, queue) => {
    const node = queue.dequeue();

    for (const neighbor of graph[node]) {
        if (visited.has(neighbor)) continue;
        visited.add(neighbor);

        queue.enqueue(neighbor);
    }
}

/**
 * https://leetcode.com/problems/graph-valid-tree/
 * Time O(E * a(N)) | Space O(V)
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function(n, edges) {
    const union = new Array(n).fill(-1)

    for (const [ src, dst ] of edges) {
        const [ x, y ] = [ find(union, src), find(union, dst) ]

        const hasCycle = x === y
        if (hasCycle) return false

        compress(union, x, y)
    }

    const isValid = edges.length === (n - 1)
    return isValid
};

const compress = (union, i, head) => union[i] = head

const find = (union, i, num = union[i]) => {
    const isEmpty = num === -1
    if (isEmpty) return i

    const head = find(union, num)

    compress(union, i, head)

    return union[i]
}