在本問題中，有根樹指滿足以下條件的 有向 圖。該樹只有一個根節(jié)點，所有其他節(jié)點都是該根節(jié)點的后繼。該樹除了根節(jié)點之外的每一個節(jié)點都有且只有一個父節(jié)點，而根節(jié)點沒有父節(jié)點。
輸入一個有向圖，該圖由一個有著 n 個節(jié)點（節(jié)點值不重復，從 1 到 n）的樹及一條附加的有向邊構(gòu)成。附加的邊包含在 1 到 n 中的兩個不同頂點間，這條附加的邊不屬于樹中已存在的邊。
結(jié)果圖是一個以邊組成的二維數(shù)組 edges 。 每個元素是一對 [ui, vi]，用以表示 有向 圖中連接頂點 ui 和頂點 vi 的邊，其中 ui 是 vi 的一個父節(jié)點。
返回一條能刪除的邊，使得剩下的圖是有 n 個節(jié)點的有根樹。若有多個答案，返回最后出現(xiàn)在給定二維數(shù)組的答案。

解題思路：分類討論 + 并查集

這道題乍一看，和684. 冗余連接非常像！只不過從無向變成了有向。
但是這個難度提升了一個喜馬拉雅山，主要是要想好一共有幾種情況，針對每種情況去解決。

1、分析

這道題分類討論非常關(guān)鍵！
這道題分類討論非常關(guān)鍵！
這道題分類討論非常關(guān)鍵！
（重要的事情說三遍，不然你會馬上暈的就不知道天南地北了）

首先我們要明確一個觀念，題目說了，人家本來就是一顆有向樹，只不過現(xiàn)在在這個基礎(chǔ)上新增了一條邊，變成了錯誤的一棵樹。而我們只要刪除一條錯誤的邊，就可以糾正了！【也就是說，即使有多種刪除方案，但只要刪除一條，而且是邊集中最右邊的那條】
——那么如何找到這條錯誤的邊呢？

● 我們先從有向樹的定義入手：
(1) 每個孩子僅有一個父節(jié)點；
(2) 有且僅有一個根節(jié)點。
??????↓
? 對應的，這條錯誤的邊（我們認為只有一條）一定導致以下異常情況之一：
● 情況一：有一個節(jié)點有兩個父節(jié)點；
?——問題：為什么不是3個，4個或者更多呢？
?因為如果是3個，我們就要刪除2條邊，4個就要刪除3條邊了！這不符合題目要求。
?——問題：那為什么不是0個呢？
?一棵標準的有向樹會有一個根節(jié)點，它的父節(jié)點是0不是很正常嗎?。?br> ● 情況二：（每個節(jié)點僅有一個父節(jié)點）沒有根節(jié)點【形成有向環(huán)】。
?——問題：會不會有多個根節(jié)點呢？
?不會！因為如果存在多個根節(jié)點，就算不刪除邊的情況下，樹都無法連通。（更何況我們還要刪除一條邊）

2、解題思路：

● 處理情況一：假設(shè)有節(jié)點node，他的兩個父節(jié)點分別是parent1、parent2。那么必然刪除邊：[parent1, node]或者[parent2, node]。
?我們可以嘗試去刪除第二條出現(xiàn)在邊集的邊，假設(shè)是[parent2, node]。
?(1) 如果刪除后，剩余邊集可以構(gòu)成一棵有向樹。那么我們直接刪除[parent2, node]即可。
?因為就算刪除第一條邊也可以構(gòu)成有向樹，但是因為我們要返回的是靠右的邊。
?(2) 如果刪除后，剩余邊集不可以構(gòu)成一棵有向樹。那么我們只能直接刪除[parent1, node]。

? 那——怎么判斷是否可以構(gòu)成有向樹？
利用并查集。定義connect[i]為節(jié)點 i 的父節(jié)點所在集合，初始每個節(jié)點的connect[i]是自己。
① 連通。如果并查集中所有節(jié)點的父節(jié)點集合是同一個，說明是連通的；
② 沒有環(huán)。是的！你沒有看錯，【異常情況一有可能會出現(xiàn)環(huán)！】
如下圖所示，如果此時刪除[3, 2]，那么會剩下環(huán)。

異常情況一：既有兩個父節(jié)點，也有環(huán)

以上兩個條件均滿足，就說明可以構(gòu)成樹！如果有一個不滿足就不能構(gòu)成樹。那么要先判斷哪個呢？

如果我們直接先進行步驟①，會導致什么結(jié)果？
此時節(jié)點1、2、4的父節(jié)點集合是什么？——無限循環(huán)，根本找不到它的父節(jié)點集合！

● 處理情況二：這里就很簡單了，和情況一的第②步處理一樣，只要出現(xiàn)環(huán)，那么這條邊一定要刪除。

? 另外，先判斷情況一，在情況一不滿足的情況下，再去處理情況二！
——為什么？你也看到了，情況二是通過環(huán)來處理的，但是情況一也可能會有環(huán)。
那我如果現(xiàn)在有環(huán)，是哪個情況呢？
如果是情況一，是刪除兩個父節(jié)點連接邊其中之一呢？還是刪除環(huán)那條呢？情況就太復雜了。
如果先處理情況一，判斷確實沒有任何一個點的父節(jié)點超過兩個。那么我們就能肯定是情況二，返回出現(xiàn)環(huán)的邊。

3、代碼實現(xiàn)

class Solution {
    private int[] connect;
    public int[] findRedundantDirectedConnection(int[][] edges) {
        // 分析題目：已經(jīng)是一個有向樹的情況下，新增一條邊，導致有向樹不滿足定義。
        //          因此，只要刪除一條有問題的邊，剩下的一定是一顆有向樹。
        
        // 看兩種不符合條件的情況
        // 1. 某一個節(jié)點存在兩個父節(jié)點
        // 2. 不是情況1時，說明每個節(jié)點僅有一個父節(jié)點，此時一定存在有向環(huán)(沒有根)

        // 初始化并查集
        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. 第一種情況：某個節(jié)點有兩個父節(jié)點(為什么現(xiàn)要判斷第一種情況呢，因為第一種情況也會出現(xiàn)環(huán)這種情況，沒辦法解耦)
        if(i < edges.length){
            // 一定是刪除其中一個父節(jié)點連接到該節(jié)點的邊

            // 如果刪除第二條出現(xiàn)的邊
            // (1) 能構(gòu)成樹，說明應該刪除第二條出現(xiàn)的邊;
            // (2) 不能構(gòu)成樹，說明應該刪除第一條邊
            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{
            // 說明此時沒有根，存在有向環(huán)
            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;
    }
    // 父節(jié)點是x, 孩子節(jié)點是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;
        }
    }
    // 如果刪除這條邊后，并查集滿足：是全連通 + 沒有環(huán)，就說明是樹
    public boolean isTree(int[][] edges, int removeIdx){
        // 環(huán)檢查
        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;
    }
}