685. Redundant Connection II

https://leetcode.com/problems/redundant-connection-ii/description/

有向图去掉一条边可以构成一棵树，问按照给定边顺序最早该去掉哪条。花花总结了三种情况:

Case1相当于无向图，用union find依次遍历并加入边，当发现当前边的两端已经在同一个连通分量时，返回当前边。

Case 2是一个结点有两个parent，需要去掉其中一条边。先遍历所有边，当有结点出现了两个parents时对应的两条边即答案候选。先选第二个出现的在图里删掉。在用UF以处理第一种方法，当发现环时且候选不为空时，把候选第一条边删掉 (Case 2.2)；否则没检测到环，意味着它已经被删过了，对应Case 2.2。

/*
 * @lc app=leetcode id=685 lang=cpp
 *
 * [685] Redundant Connection II
 *
 * https://leetcode.com/problems/redundant-connection-ii/description/
 *
 * algorithms
 * Hard (31.08%)
 * Likes:    519
 * Dislikes: 165
 * Total Accepted:    25.8K
 * Total Submissions: 82.7K
 * Testcase Example:  '[[1,2],[1,3],[2,3]]'
 *
 * 
 * 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  2
 * ⁠    ^    |
 * ⁠    |    v
 * ⁠    4 
 * 
 * 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.
 * 
 */
class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        const int N = edges.size();
        vector<int> parents(N + 1, 0); 
        vector<int> roots(N + 1, 0);
        vector<int> sizes(N + 1, 1);

        vector<int> res, res2;
        for (auto &edge : edges) {
            const int u = edge[0], v = edge[1];
            if (parents[v] > 0) {
                res = {parents[v], v};
                res2 = edge;
                edge[0] = edge[1] = -1;
            }
            parents[v] = u;
        }
        const auto find = [](vector<int> &roots, int x) {
            while (roots[x] != x) {
                roots[x] = roots[roots[x]];
                x = roots[x];
            }
            return x;
        };
        for (const auto &edge : edges) {
            const int u = edge[0], v = edge[1];
            if (u < 0 || v < 0) continue;
            if (!roots[u]) roots[u] = u;
            if (!roots[v]) roots[v] = v;
            int pu = find(roots, u);
            int pv = find(roots, v);
            if (pu == pv) return res.empty() ? edge : res;
            if (sizes[pv] > sizes[pu]) swap(pu, pv);
            roots[pv] = pu;
            sizes[pu] += sizes[pv];
        }
        return res2;
    }
};