684.冗余连接|
传送门：. - 力扣（LeetCode）
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
这个题呢有很多选择，可以用广搜也可以并查集应该还有别的办法，这里我介绍并查集的办法，我认为这道题是最适合并查集的，因为首先这道题是无向图，其次把题目转换一下就是问你连成环的边是那条边，这条边就是答案，因此并查集其实是优解
代码
class Solution {
static const int N = 1e3 + 10;
int p[N];
public:
int find(int x){
if(x == p[x]) return x;
else return p[x] = find(p[x]);
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
for(int i = 1;i <= n;i ++) p[i] = i;
for(auto arr : edges){
int a = arr[0],b = arr[1];
int A = find(a), B = find(b);
// cout << A << " " << B << endl;
if(A != B) p[A] = B;
else return arr;
}
return {};
}
};685.冗余连接||
传送门. - 力扣（LeetCode）
在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
这道题呢就复杂了一些了，变成有向图了，那么一旦变成有向图了，并查集就不好使了，这里介绍广搜的办法。
其实没有什么高级的思路，就是写bfs暴力枚举直到符合条件，写不出来的话，就要去多练代码了
这里介绍一些C++的语法
Lambda匿名函数
就比如auto bfs = [&]()：
这样的写法是在 C++ 中定义一个 Lambda 表达式（匿名函数）。这里的 bfs 是 Lambda 表达式的名称，通常用来创建一个可以在后续代码中调用的函数。让我们逐部分解析一下这个写法：
-
auto：这表示编译器会自动推导出bfs的类型。通常用于简化类型声明。 -
bfs：这是你定义的 Lambda 表达式的名称，可以用来在后面的代码中调用它。 -
[&]：这是 Lambda 表达式的捕获列表。在这里，&表示按引用捕获外部作用域的所有变量。这意味着 Lambda 表达式内部可以访问并修改外部变量。 -
()：这是 Lambda 表达式的参数列表。在这个例子中，参数列表为空，意味着这个 Lambda 不接受任何参数。 -
{}（虽然在你的例子中没有展示）：在 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 {};
}
};加油
