0684-redundant-connection.js

/**
 * https://leetcode.com/problems/redundant-connection/
 * Time O((V)^2 + E) | Space O(V + E)
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
    const graph = new Array((1000 + 1)).fill().map(() => []);

    for (const [ src, dst ] of edges) {
        const hasNodes = (src in graph) && (dst in graph)
        if (hasNodes && hasRedundantConnection(graph, src, dst)) return [ src, dst ];

        graph[src].push(dst);
        graph[dst].push(src);
    }
}

const hasRedundantConnection = (graph, source, target, seen = new Set()) => {
    if (seen.has(source)) return false
    seen.add(source);

    const isEqual = source === target
    if (isEqual) return true;

    return dfs(graph, source, target, seen);
}

const dfs = (graph, source, target, seen) => {
    for (const neighbor of graph[source]) {
        if (hasRedundantConnection(graph, neighbor, target, seen)) return true;
    }

    return false;
}

/**
 * https://leetcode.com/problems/redundant-connection/
 * Time O(V + E) | Space O(V + E)
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
    return new UnionFind(edges)
        .redundantConnection;
};

class UnionFind {
    constructor (edges) {
        this.parent = new Array(edges.length + 1).fill().map((_, index) => index);
        this.rank = new Array(edges.length + 1).fill(1);
        this.redundantConnection = [ -1, -1 ];

        this.search(edges);
    }

    search (edges) {
        for (let [ src, dst ] of edges) {
            const hasConnection = this.union(src, dst);
            if (!hasConnection) return (this.redundantConnection = [ src, dst ]);
        }
    }

    find (node, { parent } = this) {
        let head = parent[node];

        const isEqual = () => head === parent[head];
        while (!isEqual()) {
            const tail = parent[parent[head]];

            this.compress(head, tail);
            head = parent[head];
        }

        return head;
    }

    compress (tail, head, { parent } = this) {
        parent[tail] = head;
    }
    
    increaseRank (head, tail, { rank } = this) {
        rank[head] += rank[tail];
    }

    union (src, dst, { rank } = this) {
        const [ rootSrc, rootDst ] = [ this.find(src), this.find(dst) ];

        const hasCycle = rootSrc === rootDst;
        if (hasCycle) return false;

        const isSrcGreater = rank[rootDst] < rank[rootSrc];
        if (isSrcGreater) {
            this.increaseRank(rootDst, rootSrc)
            this.compress(rootSrc, rootDst)
        }

        const isDstGreater = rank[rootSrc] <= rank[rootDst];
        if (isDstGreater) {
            this.increaseRank(rootSrc, rootDst)
            this.compress(rootDst, rootSrc)
        }

        return true;
    }
}