冗余连接 II

// Problem: Given a directed graph with n nodes, represented as an edge list, where the nodes are numbered from 1 to n. The graph is initially a tree, with one additional edge added that causes a cycle or multiple parents. Our task is to find and return one edge that can be removed to form a valid tree with one root and no cycles. 
 
// Approach using Java Streams: 
// 1. Use an array to track the parent of each node. 
// 2. Traverse the edge list and detect a cycle or a node with two parents. 
// 3. If a cycle is detected, return the last edge that causes it. 
// 4. If a node has two parents, return the second edge encountered. 
 
import java.util.Arrays; 
import java.util.stream.IntStream; 
 
public class Solution { 
    public int[] findRedundantDirectedConnection(int[][] edges) { 
        int n = edges.length; 
        int[] parent = new int[n + 1]; 
        int[] candidate1 = null, candidate2 = null; 
        Arrays.fill(parent, 0); 
        for (int[] edge : edges) { 
            int u = edge[0], v = edge[1]; 
            if (parent[v] == 0) { 
                parent[v] = u; 
            } else { 
                candidate1 = new int[]{parent[v], v}; 
                candidate2 = new int[]{u, v}; 
                edge[1] = 0; 
            } 
        } 
        IntStream.range(1, n + 1).forEach(i -> parent[i] = i); 
        for (int[] edge : edges) { 
            if (edge[1] == 0) continue; 
            int u = edge[0], v = edge[1]; 
            if (find(parent, u) == v) { 
                return candidate1 == null ? edge : candidate1; 
            } 
            parent[v] = u; 
        } 
        return candidate2; 
    } 
    private int find(int[] parent, int u) { 
        return parent[u] == u ? u : (parent[u] = find(parent, parent[u])); 
    } 
}