题意
现在有一个N个点，N条边的有向图，每个节点至少与一条边相连，现在要求删掉一条边，使得有向图成为一棵树，从而可以从一个根节点遍历到其他节点（可能出现多个符合条件的答案，要求去除最后一次出现的边）
题解
大方向：并查集 冗余会出现于什么情况？ 情况1：一个节点有两个父亲，比如输入边集：[[1,2], [1,3], [2 3]] 情况2：一条边的加入导致循环，比如输入边集：[[1,2], [2,3], [3,4], [4,1], [1,5]] 如何根据冗余情况找到冗余边？ 冗余边一定出现在上面两种状态 假如没有循环边，就只是一个节点有两个父亲节点，那么就将最后加入导致分裂的边删除即可 假如出现了循环边，如果循环边的节点没有出现两个父亲节点的现象，直接将最后加入的边删除即可 加入循环子图中仍出现两个父亲节点的节点，那么不能直接删除，比如输入的是[[2,1],[3,1],[4,2],[1,4]]，虽然[1,4]这条边的加入导致了循环，但是我们要保证删除之后图仍然维持树形结构，因此删除的应该是循环子图中另一条边，此题是[2,1] 这种情况如何定位？首先我们知道，在树中，一个节点不可能有两个父亲节点，因此如果出现了这种节点，那么有问题的边一定出现在这两条边里面，如[u,v], [x, v]这两条边 然后就是判断[u,v], [x.v]哪条边出现在循环子图中即可 如何通过并查集找到冗余边？ 如果一个节点的父亲节点和当前的边的另一个端点不同，那么说明父亲节点分裂 如果一个节点和另一个节点的祖先相同，那么说明有循环
实现
class Solution {
int[]pa ;
int[]anc ;
int find(int []pa, int x){
while(pa[x] != x){
x = pa[x];
}
return x;
}
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
pa = new int[n+1];
anc = new int[n+1];
for(int i = 0 ;i < n;++i){
pa[i+1] = i+1;
anc[i+1] = i+1;
}
int []res = new int[2];
int doubleRoot = 0;
int cycle = 0;
for(int i = 0 ;i < n;++i){
int p = find(anc, edges[i][0]);
int q = find(anc, edges[i][1]);
if(pa[edges[i][1]] != edges[i][1]){
doubleRoot = i;
}else if(p == q){
cycle = i;
pa[edges[i][1]] = edges[i][0];
}else{
pa[edges[i][1]] = edges[i][0];
anc[q] = p;
}
}
if(doubleRoot == 0){
res[0] = edges[cycle][0];
res[1] = edges[cycle][1];
}else{
if(cycle > 0){
res[0] = pa[edges[doubleRoot][1]];
res[1] = edges[doubleRoot][1];
}else{
res[0] = edges[doubleRoot][0];
res[1] = edges[doubleRoot][1];
}
}
return res;
}
}
