🌕 🌕 684. 冗余连接

难度: 🌕 🌕

问题描述

---

解法

class Solution {
    int[] parent;
    public int[] findRedundantConnection(int[][] edges) {
        // 思路：
        // 并查集
        // 每次遇到一个 (from, to) 对，给 from 设置 to 作为父亲
        // 若设置成功，说明之前在不同的区块，可以连接
        // 若是设置失败，说明 from 之前已经可以连接到 to，那么该 (from, to) 对就是重复的，满足 res
        // 题目要求返回最后出现的边，那么只能从前往后遍历，第一次出现重复的节点对就是最后出现的边
        int len = edges.length;
        parent = new int[len + 1]; // 用来存储不同下标处节点的 父亲所在的下标
        // 初始化，让其指向自己，以后判断时 == 自己，说明该节点还没有设置新的父亲，可以设置父亲
        for(int i = 1; i <= len; i ++) {
            parent[i] = i;
        }
        // 遍历 (from, to) 对，尝试将它们连接
        for(int i = 0; i < len; i ++) {
            int[] array = edges[i];
            int from = array[0];
            int to = array[1];
            if(!union(from, to)) {
                return array; // 首次连接失败，返回
            }
        }
        return new int[2];
    }

    private boolean union(int from, int to) {
        // 找到 from & to 的祖先，若是一个祖先，说明该关系之前已经连接
        int fatherFrom = findFather(from);
        int fatherTo = findFather(to); 
        if(fatherFrom == fatherTo) {
            return false;
        } else {
            // 将祖先连接
            parent[fatherFrom] = parent[fatherTo];
            return true;
        }
    }

    private int findFather(int cur) {
        // 递归终止条件
        if(parent[cur] == cur) {
            return cur;
        }
        return findFather(parent[cur]);
    }
}

---

输出