题目

image.png

思路

  • 并查集

    代码

    1.   public int[] findRedundantConnection(int[][] edges) {
    2.       if (edges == null || edges.length == 0) return new int[0];
    3.       int[] s = new int[edges.length + 1];
    4.       Arrays.fill(s, -1);
    5.       for (int[] edge : edges) {
    6.           if (!union(s, edge[0], edge[1])) return edge;
    7.       }
    8.       return new int[0];
    9.   }
    11.   public boolean union(int[] s, int i, int j) {
    12.       int ri = findFC(s, i), rj = findFC(s, j);
    13.       if (ri == rj) return false;
    14.       s[ri] = rj;
    15.       return true;
    16.   }
    18.   public int findFC(int[] s, int i) {
    19.       if (i < 0 || i >= s.length) return -1;
    20.       if (s[i] < 0) return i;
    21.       s[i] = findFC(s, s[i]);
    22.       return s[i];
    23.   }

    冗余连接