[LeetCode]Redundant Connection II

和之前题目不一样的是这道题目变成了有向图。那么变为有向图之后，我们对directed tree加上一条边和undirected tree有什么区别呢。可能会有以下三种状况：

1. 仍然存在环，比如[1, 2], [2,3], [3,1]
2. 不存在环但是存在某一个节点有两个父节点，比如[2,1], [3,1], [2, 3]
3. 1和2的情况同时存在，比如[2,1], [3,1], [1,4], [4,2]

所以和I的解法不同，这里每一种情况我们都要判断并删除相应的边，具体算法如下：

1. 如果是情况1，根据题目的要求，我们删除边e。e满足条件，按照题目给定的边的顺序依次加上边，当加上e的时候，第一次出现环
2. 如果是情况2，删除一条通向v的边。v满足条件其有两个父节点。e满足条件其在题目给定的边的顺序中比另外一条通向v的边出现较后
3. 如果是情况3，删除一条通向v的边。v满足条件其有两个父节点。e满足条件其在环上

我们只需要对这三种情况分别处理即可，DFS显然可以解，我们只需要记录环的路径（如果存在）和拥有两个父节点的v的对应的入射边（如果存在）。然后对于以上三种情况分别处理。但是DFS的解法需要我们建图。和I一样，我们可以用Union Find，这样省去了建图的步骤更为效率。在Union Find中我们也要对环和拥有两个父节点的v分别记录然后根据以上算法处理。关于Union Find的介绍可以参考这篇文章。代码如下：