In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.
Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given directed graph will be like this: 1 / v v 2-->3
Example 2:
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
^ |
| v
4 <- 3
Note:
- The size of the input 2D-array will be between 3 and 1000.
- Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
class Solution { int[] anc;//并查集 int[] parent;// record the father of every node to find the one with 2 fathers,记录每个点的父亲，为了找到双入度点 public int[] findRedundantDirectedConnection(int[][] edges) { anc=new int[edges.length+1]; parent=new int[edges.length+1]; int[] edge1=null; int[] edge2=null; int[] lastEdgeCauseCircle=null; for (int[] pair:edges){ int u=pair[0]; int v=pair[1]; if(anc[u]==0) anc[u]=u; if(anc[v]==0) anc[v]=v;//init the union-find set 初始化并查集 if (parent[v]!=0){// node v already has a father, so we just skip the union of this edge and check if there will be a circle ，跳过 edge2,并记下 edge1,edge2 edge1=new int[]{parent[v],v}; edge2=pair; } else { parent[v]=u; int ancU=find(u); int ancV=find(v); if(ancU!=ancV){ anc[ancV]=ancU; } else { //meet a circle , 碰到了环 lastEdgeCauseCircle=pair; } } } if (edge1!=null&&edge2!=null) return lastEdgeCauseCircle==null?edge2:edge1; //如果是情况2、3，则根据有没有碰到环返回 edge1 或 edge2 else return lastEdgeCauseCircle; //否则就是情况1，返回那个导致环的最后出现的边。 } private int find(int node){ if (anc[node]==node) return node; anc[node]=find(anc[node]); return anc[node]; } }
https://leetcode.com/problems/redundant-connection-ii/discuss/278105/topic
分三种情况解决，唯一缺陷是少了path compression