Leetcode刷题 | Day60_图论06

【题目描述】

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：

现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图

先请你找出冗余边，删除后，使该图可以重新变成一棵树。

【输入描述】

第一行包含一个整数 N，表示图的节点个数和边的个数。

后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。

【输出描述】

输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。

那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

#include <iostream>
#include <vector>
using namespace std;int n; // 节点数量
vector<int> father(1001, 0); // 按照节点大小范围定义数组// 并查集初始化
void init() {for (int i = 0; i <= n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]);
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}int main() {int s, t;cin >> n;init();for (int i = 0; i < n; i++) {cin >> s >> t;if (isSame(s, t)) {cout << s << " " << t << endl;return 0;} else {join(s, t);}}
}

【题目描述】

有一种有向树,该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：

现在有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。

【输入描述】

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

【输出描述】

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。

核心函数解释

1. 函数 getRemoveEdge

void getRemoveEdge(const vector<vector<int>>& edges) {init();  // 初始化并查集for (int i = 0; i < n; i++) {if (isSame(edges[i][0], edges[i][1])) {  // 检查当前边的两个端点是否已在同一集合cout << edges[i][0] << " " << edges[i][1] << endl;  // 输出形成环的边return;}else {join(edges[i][0], edges[i][1]);  // 合并两个集合}}
}

这个函数用于处理"情况三"：当图中没有入度为2的节点时，我们需要找出形成环的边。原理是：

• 初始化并查集，每个节点自成一个集合
• 按顺序遍历所有边
• 对于每条边，检查其两个端点是否已经在同一个集合中
• 如果在同一集合中，说明添加这条边会形成环，它就是要删除的边
• 否则，将这条边加入图中（合并两个端点所在集合）

2. 函数 isTreeAfterRemoveEdge

bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {init();  // 初始化并查集for (int i = 0; i < n; i++) {if (i == deleteEdge) continue;  // 跳过要删除的边if (isSame(edges[i][0], edges[i][1])) {  // 检查添加当前边是否会形成环return false;  // 如果形成环，说明不是树}else {join(edges[i][0], edges[i][1]);  // 合并两个集合}}return true;  // 如果没有形成环，说明是树
}

这个函数用于检测删除某条边后，剩余的图是否是一棵树。原理是：

• 初始化并查集
• 遍历所有边，跳过要删除的边
• 对于每条边，检查添加它是否会形成环
• 如果形成环，则删除这条边后的图不是树，返回false
• 如果不形成环，则删除这条边后的图是树，返回true

为什么两个函数都要初始化并查集？

两个函数都需要初始化并查集的原因是：

1. 独立的图分析：每个函数都在进行独立的图分析操作。它们需要从一个全新的、没有边的图开始，然后按照自己的逻辑添加边。
2. 状态重置：并查集是一种数据结构，它的状态会随着操作（如join）而改变。为了保证每次函数调用时，并查集都处于初始状态，需要进行初始化。
3. 功能封装：这种设计使得函数更加封装和独立，不依赖于外部的并查集状态，增强了代码的可维护性。

主函数逻辑

主函数中的逻辑是处理三种可能的情况：

1. 有入度为2的节点（情况一和情况二）：
   • 找出所有入度为2的节点对应的边
   • 尝试删除每条边，并检查剩余的图是否是树
   • 优先删除最后出现的边（通过倒序遍历实现）
2. 没有入度为2的节点（情况三）：
   • 使用getRemoveEdge函数找出形成环的边

这种设计考虑了不同类型的有向图可能有不同的冗余边情况，并针对每种情况提供了相应的处理逻辑。

#include <iostream>
#include <vector>
using namespace std;int n = 0;
vector<int> father(1001, 0);
// 并查集初始化
void init() {for (int i = 1; i <= n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u);v = find(v);if (u == v) return ;father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 在有向图里找到删除的那条边，使其变成树
void getRemoveEdge(const vector<vector<int>>& edges) {init();for (int i = 0; i < n; i++) {if (isSame(edges[i][0], edges[i][1])) {cout << edges[i][0] << " " << edges[i][1] << endl;return;}else {join(edges[i][0], edges[i][1]);}}
}
// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {init(); // 初始化并查集for (int i = 0; i < n; i++) {if (i == deleteEdge) continue; // 删除这条边，不操作if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树return false;}else {join(edges[i][0], edges[i][1]);}}return true;
}
int main() {int s, t;vector<vector<int>> edges;cin >> n;vector<int> inDegree(n + 1, 0); // 记录节点入度for (int i = 0; i < n; i++) {cin >> s >> t;inDegree[t]++;edges.push_back({s, t}); // 把边都存进二维数组}vector<int> vec; // 记录入度为2的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}}// 情况一、情况二if (vec.size() > 0) {// 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边if (isTreeAfterRemoveEdge(edges, vec[0])) {cout << edges[vec[0]][0] << " " << edges[vec[0]][1];} else {cout << edges[vec[1]][0] << " " << edges[vec[1]][1];}return 0;}// 处理情况三// 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了getRemoveEdge(edges);return 0;
}