一棵树有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){  // 入度为2conflict = 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;}
}