在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
解题思路：分类讨论 + 并查集
这道题乍一看，和684. 冗余连接非常像！只不过从无向变成了有向。
但是这个难度提升了一个喜马拉雅山，主要是要想好一共有几种情况，针对每种情况去解决。
1、分析
这道题分类讨论非常关键！
这道题分类讨论非常关键！
这道题分类讨论非常关键！
（重要的事情说三遍，不然你会马上晕的就不知道天南地北了）
首先我们要明确一个观念，题目说了，人家本来就是一颗有向树，只不过现在在这个基础上新增了一条边，变成了错误的一棵树。而我们只要删除一条错误的边，就可以纠正了！【也就是说，即使有多种删除方案，但只要删除一条，而且是边集中最右边的那条】
——那么如何找到这条错误的边呢？
● 我们先从有向树的定义入手：
(1) 每个孩子仅有一个父节点；
(2) 有且仅有一个根节点。
↓
⭐ 对应的，这条错误的边（我们认为只有一条）一定导致以下异常情况之一：
● 情况一：有一个节点有两个父节点；
——问题：为什么不是3个，4个或者更多呢？
因为如果是3个，我们就要删除2条边，4个就要删除3条边了！这不符合题目要求。
——问题：那为什么不是0个呢？
一棵标准的有向树会有一个根节点，它的父节点是0不是很正常吗！！
● 情况二：（每个节点仅有一个父节点）没有根节点【形成有向环】。
——问题：会不会有多个根节点呢？
不会！因为如果存在多个根节点，就算不删除边的情况下，树都无法连通。（更何况我们还要删除一条边）
2、解题思路：
● 处理情况一：假设有节点node，他的两个父节点分别是parent1、parent2。那么必然删除边：[parent1, node]或者[parent2, node]。
我们可以尝试去删除第二条出现在边集的边，假设是[parent2, node]。
(1) 如果删除后，剩余边集可以构成一棵有向树。那么我们直接删除[parent2, node]即可。
因为就算删除第一条边也可以构成有向树，但是因为我们要返回的是靠右的边。
(2) 如果删除后，剩余边集不可以构成一棵有向树。那么我们只能直接删除[parent1, node]。
⭕ 那——怎么判断是否可以构成有向树？
利用并查集。定义connect[i]为节点 i 的父节点所在集合，初始每个节点的connect[i]是自己。
① 连通。如果并查集中所有节点的父节点集合是同一个，说明是连通的；
② 没有环。是的！你没有看错，【异常情况一有可能会出现环！】
如下图所示，如果此时删除[3, 2]，那么会剩下环。
判断是否有环：就很简单了，根据并查集，【如果父节点的connect集合和子节点的connect集合一样，就说明如果加入这条边会导致有向环！】，此时不能构成有向树。
以上两个条件均满足，就说明可以构成树！如果有一个不满足就不能构成树。那么要先判断哪个呢？
如果我们直接先进行步骤①，会导致什么结果？
此时节点1、2、4的父节点集合是什么？——无限循环，根本找不到它的父节点集合！
● 处理情况二：这里就很简单了，和情况一的第②步处理一样，只要出现环，那么这条边一定要删除。
⭐ 另外，先判断情况一，在情况一不满足的情况下，再去处理情况二！
——为什么？你也看到了，情况二是通过环来处理的，但是情况一也可能会有环。
那我如果现在有环，是哪个情况呢？
如果是情况一，是删除两个父节点连接边其中之一呢？还是删除环那条呢？情况就太复杂了。
如果先处理情况一，判断确实没有任何一个点的父节点超过两个。那么我们就能肯定是情况二，返回出现环的边。
3、代码实现
class Solution {
private int[] connect;
public int[] findRedundantDirectedConnection(int[][] edges) {
// 分析题目：已经是一个有向树的情况下，新增一条边，导致有向树不满足定义。
// 因此，只要删除一条有问题的边，剩下的一定是一颗有向树。
// 看两种不符合条件的情况
// 1. 某一个节点存在两个父节点
// 2. 不是情况1时，说明每个节点仅有一个父节点，此时一定存在有向环(没有根)
// 初始化并查集
connect = new int[edges.length + 1];
for(int i=0; i<connect.length; i++){
connect[i] = i;
}
int[] indegree = new int[edges.length+1];
int i = 0;
for(; i<edges.length; i++){
indegree[edges[i][1]]++;
if(indegree[edges[i][1]] > 1) break;
}
// 1. 第一种情况：某个节点有两个父节点(为什么现要判断第一种情况呢，因为第一种情况也会出现环这种情况，没办法解耦)
if(i < edges.length){
// 一定是删除其中一个父节点连接到该节点的边
// 如果删除第二条出现的边
// (1) 能构成树，说明应该删除第二条出现的边;
// (2) 不能构成树，说明应该删除第一条边
int j = 0;
for(; j<edges.length; j++){
if(edges[j][1] == edges[i][1]) break;
}
if(isTree(edges, i)) return new int[]{edges[i][0], edges[i][1]};
else return new int[]{edges[j][0], edges[j][1]};
}else{
// 说明此时没有根，存在有向环
i = 0;
for(; i<edges.length; i++){
if(!merge(edges[i][0], edges[i][1])) break;
}
return new int[]{edges[i][0], edges[i][1]};
}
}
public int find(int x){
while(x != connect[x]){
x = connect[x];
}
return x;
}
// 父节点是x, 孩子节点是y，有x→y
public boolean merge(int x, int y){
int x_root = find(x);
int y_root = find(y);
if(x_root == y_root) return false;
else{
connect[y_root] = x_root; // 有向，必须是这个合并顺序
return true;
}
}
// 如果删除这条边后，并查集满足：是全连通 + 没有环，就说明是树
public boolean isTree(int[][] edges, int removeIdx){
// 环检查
for(int i=0; i<edges.length; i++){
if(i == removeIdx) continue;
if(!merge(edges[i][0], edges[i][1])) return false;
}
// 是全连通图
int root = -1;
for(int i=1; i<connect.length; i++){
int tmp = find(i);
if(root == -1) root = tmp;
else if(tmp != root) return false;
}
return true;
}
}
