冗余连接

/*
 * 思路：
 * 1. 使用并查集（Union-Find）算法来检测图中的环。
 * 2. 使用Java Stream进行操作。
 * 3. 对边列表进行过滤，找到形成环的最后一条边。
 */

import java.util.stream.IntStream;

public class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = IntStream.rangeClosed(0, n).toArray();
        
        return IntStream.range(0, n)
                .mapToObj(i -> edges[i])
                .filter(edge -> find(parent, edge[0]) == find(parent, edge[1]) || !union(parent, edge[0], edge[1]))
                .reduce((first, second) -> second) // 获取最后一条冗余边
                .orElse(new int[0]);
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
    
    private boolean union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            return true;
        }
        return false;
    }
}