并查集

[TieMuZhen]

前言

首先要知道并查集可以解决什么问题呢？

主要就是集合问题，两个节点在不在一个集合，也可以将两个节点添加到一个集合中。

题目

LeetCode 684

/**
 * @param {number[][]} edges
 * @return {number[]}
 */

var findRedundantConnection = function(edges) {
    let parents = new Array(edges.length + 1);
    // 并查集初始化
    for(let i = 0; i < edges.length + 1; i++){
        parents[i] = i;
    }
    // 并查集里寻根的过程
    var find = function(n) {
        if(n != parents[n]){
            return parents[n] = find(parents[n]);
        }
        return n;
    }

    // 将a->b 这条边加入并查集
    var join = function(a, b){
        let p1 = find(a);
        let p2 = find(b);
        if(p1 != p2){
            parents[p1] = p2;
        }
    }
    // 判断 u 和 v是否找到同一个根
    var same = function(a, b){
        let p1 = find(a);
        let p2 = find(b);
        return p1 == p2;
    }
    for(let i = 0; i < edges.length; i++){
        if(same(edges[i][0], edges[i][1])){
            return edges[i];
        }else{
            join(edges[i][0], edges[i][1]);
        }
    }
    return [];
};