leetcode - 684. 冗余连接

684. 冗余连接

解决思路

大致上的思路就是将元素加入到 并查集 中，那么在遍历到边的时候先去判断的边的两个端点的 根节点 是否相等，如果相等，那么就代表此刻把这条边加上去就形成了环【可以这么理解，如果形成了环，那么两个端点在环内从那个端点出发都可以到达环内所有节点，只是这里提取出共同的 根节点罢了】

并查集

并查集（Union Find）：一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。不交集指的是一系列没有重复元素的集合。

• 合并（Union）：将两个集合合并成一个集合。
• 查找（Find）：确定某个元素属于哪个集合。通常是返回集合内的一个「代表元素」。

并查集代码例子

public class UnionFind {

    public static class Element<V> {
        public V value;

        public Element(V value) {
            this.value = value;
        }
    }

    public static class UnionFindSet<V> {
        public HashMap<V, Element<V>> elementMap;
        // key: 某个元素，value: 该元素的父
        public HashMap<Element<V>, Element<V>> fatherMap;
        // key: 某个集合的代表元素，value: 该集合的大小
        public HashMap<Element<V>, Integer> sizeMap;

        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V value : list) {
                Element<V> element = new Element<>(value);
                elementMap.put(value, element);
                // 初始化都是自己指向自己，也就是代表元素
                fatherMap.put(element, element);
                sizeMap.put(element, 1);
            }
        }

        /**
         * 给定一个 element，往上一直找，把代表元素（fatherMap 指向自己的为代表元素）返回
         * @param element
         * @return
         */
        public Element<V> findHead(Element<V> element) {
            Stack<Element<V>> path = new Stack<>();
            // 查找代表元素
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }
            while (!path.isEmpty()) {
                // 将路径上的 element，直接指向 代表元素，加快下次的查找速度
                fatherMap.put(path.pop(), element);
            }
            return element;
        }


        /**
         * 判断是不是在同一个集合
         * @return
         */
        public boolean isSameSet(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }

        /**
         * 将两个集合合并，小的集合加入大的集合中
         * @param a
         * @param b
         */
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Element aF = findHead(elementMap.get(a));
                Element bF = findHead(elementMap.get(b));
                if (aF != bF) {
                    Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
                    Element<V> small = big == aF ? bF : aF;
                    fatherMap.put(small, big);
                    sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
                    // 不是代表元素了，所以删除掉
                    sizeMap.remove(small);
                }
            }
        }
    }

}

解决

参考链接：. - 力扣（LeetCode）

/**
 * 使用 并查集的 方法【参考官方】
 * 执行用时分布 1 ms 击败 62.07% 复杂度分析 消耗内存分布 42.10 MB 击败 61.45%
 * @param edges
 * @return
 */
public int[] findRedundantConnection(int[][] edges) {
    int[] parent = new int[edges.length + 1];
    // 初始化，将所有的节点指向自己
    for (int i = 0; i < parent.length; i++) {
        parent[i] = i;
    }
    for (int[] edge : edges) {
        int node1 = edge[0];
        int node2 = edge[1];
        // 如果父节点一样，代表已经形成环了
        if (findHead(parent, node1) == findHead(parent, node2)){
            return edge;
        }
        union(parent, edge);
    }
    return new int[0];
}

/**
 * 查找 根节点，并将 递归路径上的 节点都指向 根节点
 */
public int findHead(int[] parent, int element){
    if (parent[element] != element){
        // 递归获取根节点
        parent[element] = findHead(parent, parent[element]);
    }
    return parent[element];
}

/**
* 将数据加入到  并查集
*/
public void union(int[] parent, int[] edge){
  // 只是一个方向性的问题
  // 就是获取到 端点 0 的根节点，然后将它指向 端点 1 的根节点
  // 这种做法是为了直接指向根节点，如果是直接指向，会造成不是指向自己的根节点
  parent[findHead(parent, edge[0])] = findHead(parent, edge[1]);
}