题目描述

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。
每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，
用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。
若有多个答案，返回最后出现在给定二维数组的答案。

样例

示例 1:

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3
示例 2:

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3
注意:

二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

算法1

(并查集) $O(n)$

首先树，不能有环， 其次不能有两个父节点同时指向一个孩子节点，也就是不能有入度为2的节点

• 因此分为两种情况
  • 构成环
  • 入度为2的点， 去掉其中一条边，使其入度为变为1
    • 如果入度为2的点还参与形成了环，那么就应该删除构成环的那一条
    • 否则，随便删除其中一条即可，按照题目要求，返回数组中的靠后的边

时间复杂度

• 遍历数对$O(n)$
• 并查集 ～$O(n)$

C++ 代码

class Solution {
public:
    vector<int> p;

    int find(int x ){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void merge(int x, int y){
        p[find(x)] = find(y);
    }

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        p.resize(n + 1);
        for(int i = 1; i <= n; i++) p[i] = i;

        // 找入度为2的节点
        vector<int> in_degree(n + 1, 0);
        int k = -1;
        for(auto &e : edges){
            in_degree[e[1]] ++;
            if(in_degree[e[1]] == 2) k = e[1];
        }

        vector<int> in_degree_equal_2;
        for(auto &e : edges){
            int a = e[0], b = e[1];
            if(b == k){
                in_degree_equal_2.push_back(a);
                continue;
            }
            if(find(a) == find(b))  return e;
            else merge(a, b);
        }

        if(find(in_degree_equal_2[0]) == find(k)) return {in_degree_equal_2[0], k};
        else return {in_degree_equal_2[1], k};  // 返回构成环 或者是 考后的那条边
    }
};