【并查集】685. 冗余连接II

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 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]，那么会剩下环。

异常情况一：既有两个父节点，也有环

以上两个条件均满足，就说明可以构成树！如果有一个不满足就不能构成树。那么要先判断哪个呢？

如果我们直接先进行步骤①，会导致什么结果？
此时节点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;
    }
}