传送门. - 力扣（LeetCode）

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

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

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

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

这道题呢就复杂了一些了，变成有向图了，那么一旦变成有向图了，并查集就不好使了，这里介绍广搜的办法。

其实没有什么高级的思路，就是写bfs暴力枚举直到符合条件，写不出来的话，就要去多练代码了

这里介绍一些C++的语法

Lambda匿名函数

就比如auto bfs = [&]()：

这样的写法是在 C++ 中定义一个 Lambda 表达式（匿名函数）。这里的 bfs 是 Lambda 表达式的名称，通常用来创建一个可以在后续代码中调用的函数。让我们逐部分解析一下这个写法：

1. auto：这表示编译器会自动推导出 bfs 的类型。通常用于简化类型声明。

2. bfs：这是你定义的 Lambda 表达式的名称，可以用来在后面的代码中调用它。

3. [&]：这是 Lambda 表达式的捕获列表。在这里，& 表示按引用捕获外部作用域的所有变量。这意味着 Lambda 表达式内部可以访问并修改外部变量。

4. ()：这是 Lambda 表达式的参数列表。在这个例子中，参数列表为空，意味着这个 Lambda 不接受任何参数。

5. {}（虽然在你的例子中没有展示）：在 Lambda 表达式中，函数体用大括号 {} 包围。在这里，你可以编写要执行的代码逻辑。

remove函数

remove(g[x].begin(), g[x].end(), y)：std::remove 是一个算法，用于重新排列容器的元素。它会把所有与 y 相等的元素移动到容器的末尾，并返回一个指向新逻辑尾部的迭代器。注意，这并不会真正删除这些元素，而是通过移动它们来“删除”。

• g[x].begin() 和 g[x].end() 分别是 g[x] 的起始和结束迭代器。
• y 是要删除的元素。

配合erase用

erase函数

g[x].erase(..., g[x].end())：erase 是 std::vector 的成员函数，用于真正删除元素。它接受两个迭代器作为参数，删除这两个迭代器之间的元素。在这里，第一个参数是 std::remove 返回的新逻辑尾部的迭代器，第二个参数是 g[x].end()。

代码

class Solution {
    static const int N = 1e3 + 10;
    int ind[N];
    bool st[N];
    vector<int> e[N];
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for(auto arr : edges){
            int x = arr[0], y = arr[1];
            ind[y] ++, e[x].push_back(y);
        }

        auto bfs = [&](){
            memset(st,false,sizeof(st));

            queue<int> q;
            for(int i = 1;i <= n;i ++){
                if(!ind[i]) q.push(i);
            }

            if(q.empty() || q.size() > 1) return false;

            int sum = 1;
            while(!q.empty()){
                auto t = q.front();
                q.pop();
                st[t] = true;

                for(auto x : e[t]){
                    if(st[x]) continue;
                    q.push(x);
                    sum ++;
                }
            }

            return sum == n; 
        };

        for(int i = n - 1;i >= 0;i --){
            int x = edges[i][0], y = edges[i][1];
            ind[y] --;
            e[x].erase(remove(e[x].begin(), e[x].end(), y), e[x].end());
            if(bfs()) return edges[i];
            ind[y] ++;
            e[x].push_back(y);
        }

        return {};
    }
};

 加油