leetcode 685. Redundant Connection II 有向图的环的查询 + 并查集Union Find

素颜马尾好姑娘i 2022-06-03 09:24 106阅读 0赞

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair \[u, v\] that represents a directed edge connecting nodes u and v, where u is a parent of child v.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:  
Input: \[\[1,2\], \[1,3\], \[2,3\]\]  
Output: \[2,3\]  
Explanation: The given directed graph will be like this:  
1  
/ \\  
v v  
2–>3  
Example 2:  
Input: \[\[1,2\], \[2,3\], \[3,4\], \[4,1\], \[1,5\]\]  
Output: \[4,1\]  
Explanation: The given directed graph will be like this:  
5 <- 1 -> 2  
^ |  
| v  
4 <- 3  
Note:  
The size of the input 2D-array will be between 3 and 1000.  
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

有向图里找环路，也可以理解为，找出使得tree 结构invalid的那个边。  
无向图里，我么可以用深度优先，或者union-find，用一个点发散代表一个连通分量，但是有向图里，本来一个点只有一个parent关系，添加一条边，使得一个点可能有两个parent，没有办法直接用之前的算法。

首先理清楚一共这种invalid一共包含哪些情况。判断的依据是什么。  
一个valid的tree结构，除了root结点之外，每个点有且只有一个parent点，加入一条冗余边之后，要么使得一个非root结点有两个parent，要么使得root结点有parent。  
所以我们的算法里，首先找出是否有一个点有两个parent。这里我们用hash table，以子节点为key, 母结点为value，建立对应联系。  
找到之后，将其中一条边作废。然后再在新的图中使用union-find，或者是深度优先算法。如果还有环路出现，代表两种可能性，要么是环路是指向root节点的，表现为，第一轮hash查找种没有发现有两个parent的节点，要么是我们废的那条边不是多余边，则废另外那条。  
如果新的图没有环路了，那么证明，我们废的那条边是正确的，返回那条边即可。

建议和[leetcode 721. Accounts Merge 并查集Union Find][leetcode 721. Accounts Merge _Union Find]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class DSU 
    {
    private:
        vector<int> parent;
    public:
        DSU(int size) 
        {
            parent.reserve(1001);
            for (int i = 0; i <= size; i++) 
            {
                parent[i] = i;
            }
        }
    
        int find(int v) 
        {
            if (parent[v] == v) 
                return parent[v];
            else 
                parent[v] = find(parent[v]);
            return parent[v];
        }
    
        bool Union(int u, int v) 
        {
            int pu = find(u);
            int pv = find(v);
            if (pu == pv) 
                return false;
            parent[pv] = pu;
            return true;
        }
    };
    
    class Solution {
    public:
        vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) 
        {
            map<int, int> hash;
            vector<int> cand1;
            vector<int> cand2;
            for (auto &e : edges)
            {
                if (hash.find(e[1]) != hash.end()) 
                {
                    cand1 = { hash[e[1]], e[1] };
                    cand2 = e;
                    e[1] = 0;
                    break;
                }
                else 
                {
                    hash[e[1]] = e[0];
                }
            }
    
            DSU dsu(edges.size());
            for (auto &e : edges) 
            {
                if (e[1] == 0) continue;
                if (!dsu.Union(e[0], e[1])) 
                {
                    if (cand1.empty()) 
                        return e;
                    return cand1;
                }
            }
            return cand2;
        }
    };

[leetcode 721. Accounts Merge _Union Find]: http://blog.csdn.net/jackzhang_123/article/details/78885245