一棵树有n个点和n条边，返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。
解释：
注意不冗余的有根树的特性！**根节点入度为0，其余结点只有一个入度！**所以冗余的两种情况如下：
（1）有一个结点有2个入度（破环其他结点只有一个入度的条件）（可能成环可能不成环）
（2）形成一个每个节点都只有一个入度的环（破环根节点入度为0的条件）（成环）
对于情况（1），找到入度为2的结点（只关注入度值）然后返回冗余的边就行了，但是：
1）当不成环时，返回任意一条都行
2）当成环时，要返回构成环的那条
所以这里只处理不成环的情况，入度为2时的边记为conflict，并跳过这种可能会导致冗余的边（无论是情况1)的真冗余边还是2)的非冗余边）。把成环的情况合并成到（2）解决。
（所以这里的情况2)出现时，可能造成冗余的边将被跳过）
（a）没去掉真正的冗余边，会出现情况（2）成环
或者(b)去掉了真正的冗余边，不会出现情况（2）
对（2），入度不为2的结点需要判定是否成环。如果该结点入度不为2，且属于同一个并查集，说明成环
记录形成有向环的那条边为circle，最后删掉构成环的边就可以了。
由于肯定存在一条冗余边，如果只有circle，那就是circle，如果只有conflict，那就是conflict，如果两个都有，说明是（1）的成环的情况（a）
但是！可能得到circle时是这样！构成环 的临门一脚不一定就是要删的那个，左边那个才是真正要删的！
所以需要用一个祖先数组ancestors记录“上一个结点”，要找到这个冗余边，就是找 指向edges[conflict][1]的上一个结点
因为只有入度不为2才会更新ancestors，所以ancestors记录的边必然排除了conflict记录的那条。有了ancestors，也不用存入度了，直接：如果ancestors[v]!=v，说明有其他父节点（入度为2）
即：冗余边为
（ancestors[edges[conflict][1]], edges[conflict][1]）
class UnionFind{
int[] parents;
UnionFind(int l){
parents = new int[l];
Arrays.fill(parents, -1);
}
int find(int x){
if (parents[x] < 0) {
return x; // 如果是根节点，则返回
}
// 路径压缩
return parents[x] = find(parents[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (parents[rootX] < parents[rootY]) { // 负数 <说明rootY下标的结点数更少
parents[rootX] += parents[rootY];
parents[rootY] = rootX; // 小树合并到大树
}else{
parents[rootY] += parents[rootX];
parents[rootX] = rootY; // 小树合并到大树
} // 否则parent[rootX] = parent[rootY]，不管
}
}
}
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int conflict = -1; // 冲突（俩父节点）
int cycle = -1; // 环
int[] parent = new int[edges.length];
for(int i=0; i<edges.length; i++){
parent[i] = i; // 要记录指向环路那个！！
}
UnionFind uf = new UnionFind(edges.length);
for(int i=0; i<edges.length; i++){
int u = edges[i][0]-1, v = edges[i][1]-1;
if(parent[v]!=v){ // 入度为2
conflict = i; // 冲突，v有俩父结点不同的路径
}else{ // 判断是否成环
if(uf.find(u)==uf.find(v)){ // 成环
cycle = i;
}else{ // 正常
parent[v] = u; // u是v的父节点
uf.union(u, v);
}
}
}
if(conflict==-1){ // 只存在环路
return edges[cycle];
}
if(cycle==-1){ // 只存在冲突
return edges[conflict];
}
// 都有，则附加的边不可能是 [u,v]
//（因为[u,v] 已经被记为导致冲突的边，不可能被记为导致环路出现的边），
// 因此附加的边是 [parent[v],v]。
int[] res = {parent[edges[conflict][1]-1]+1, edges[conflict][1]};
return res;
}
}
