【算法与数据结构】684、685、LeetCode冗余连接I II

文章目录

一、684、冗余连接 I
二、685、冗余连接 II
三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、684、冗余连接 I

在这里插入图片描述

思路分析：题目给出一个无向有环图，要求去掉一个边以后构成一个树（多叉树）。那么我们根据并查集理论，将所有的边加入到并查集中，前面的边先连上，边上的两个节点如果不在同一个集合中，就加入集合。如果两个节点已经出现在同一集合里，说明这两个节点已经连接在一起了，再加入一条后来的边就会构成环。因此去掉后来的这条边即可。

程序如下：

class Solution {
private:int n = 200005;		// 节点数量 200000vector<int> father = vector<int>(n, 0);	// C++里面的一种数据结构// 并查集初始化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;      // 根不同，则令v的父节点为u}
public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();for (int i = 0; i < edges.size(); i++) {if (isSame(edges[i][0], edges[i][1])) return edges[i];else join(edges[i][0], edges[i][1]);}return { };}
};

复杂度分析：

时间复杂度： $O (n l o g n)$ ，其中 $n$ 是图中边的个数，即edges数组的大小。需要遍历图中的 $n$ 条边，对于每条边，需要对两个节点查找祖先，如果两个节点的祖先不同则需要进行合并，需要进行2次查找和最多1次合并。一共需要进行 $2 n$ 次查找和最多 $n$ 次合并，因此总时间复杂度是 $\log ⁡n)=O(n \log n)$ 。
空间复杂度： $O (n)$ ，主要开销用于father数组。

二、685、冗余连接 II

在这里插入图片描述

思路分析：题目说明，图原本是一棵树，只不过在不增加节点的情况下多了一条额外的边，我们需要把多出来的这一条边去除。与684题区别在于本题是有向图，684题是无向图。关于有向图有出度和入度的说法。出度是指节点发出的箭头数量，入度是指指向节点的箭头数量。根节点没有父节点，其他节点有且只有一个父节点，那么多出来的一条边就会改变了节点的入度数量，而出度的数量无法成为判断标准（一个父节点可以由多个子节点，出度数量不唯一）。出现入度为2的节点有以下两种情况：

在这里插入图片描述

如果加入的这条边形成了有向环，那么入度不会改变：
在这里插入图片描述
统计节点入度：

int inDegree[N] = {0}; // 记录节点入度
n = edges.size(); // 边的数量
for (int i = 0; i < n; i++) {inDegree[edges[i][1]]++; // 统计入度
}

前两种入度为2的情况一定是删除入度为2的节点的两条边其中一条。题目还要求返回最后出现在二维数组的答案，也就是说要从后往前遍历，删除以后判断剩下的图是否构成树。如果说两条边都可以构成树，就删除最后一条边。

vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
// 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案
for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}
}
// 处理图中情况1 和 情况2
// 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
if (vec.size() > 0) {if (isTreeAfterRemoveEdge(edges, vec[0])) {return edges[vec[0]];} else {return edges[vec[1]];}
}

情况三，明确没有入度为2的情况，一定是有环，我们从后往前遍历，找到删除以后的那个可以构成树的边。那么如何判断一个图是否为树，应该应用到并查集了。因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根，那么这条边添加上之后这个图一定不是树了。

// 情况三：在有向图里找到删除的那条边，使其变成树vector<int> getRemoveEdge(const vector<vector<int>>& edges) {init(); // 初始化并查集for (int i = 0; i < n; i++) { // 遍历所有的边if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边return edges[i];}join(edges[i][0], edges[i][1]);}return {};}

程序如下：

// 685、冗余连接II-并查集
class Solution2 {
private:static const int N = 1005;		// 节点数量 1005int father[N];int n;                          // 边的数量// 并查集初始化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;      // 根不同，则令v的父节点为u}// 情况三：在有向图里找到删除的那条边，使其变成树vector<int> getRemoveEdge(const vector<vector<int>>& edges) {init(); // 初始化并查集for (int i = 0; i < n; i++) { // 遍历所有的边if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边return edges[i];}join(edges[i][0], edges[i][1]);}return {};}// 删一条边之后判断是不是树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;}join(edges[i][0], edges[i][1]);}return true;}
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int inDegree[N] = { 0 }; // 记录节点入度n = edges.size(); // 边的数量for (int i = 0; i < n; i++) {inDegree[edges[i][1]]++; // 统计入度}vector<int> vec; // 记录入度为2的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}}// 情况一和情况二：如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树if (vec.size() > 0) {if (isTreeAfterRemoveEdge(edges, vec[0])) {return edges[vec[0]];}else {return edges[vec[1]];}}// 情况三：明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了return getRemoveEdge(edges);}
};

复杂度分析：

时间复杂度： $\log n)$ 。
空间复杂度： $O (n)$ 。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;// 684、冗余连接I-并查集
class Solution {
private:int n = 200005;		// 节点数量 200000vector<int> father = vector<int>(n, 0);	// C++里面的一种数据结构// 并查集初始化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;      // 根不同，则令v的父节点为u}
public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();for (int i = 0; i < edges.size(); i++) {if (isSame(edges[i][0], edges[i][1])) return edges[i];else join(edges[i][0], edges[i][1]);}return { };}
};// 685、冗余连接II-并查集
class Solution2 {
private:static const int N = 1005;		// 节点数量 1005int father[N];int n;                          // 边的数量// 并查集初始化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;      // 根不同，则令v的父节点为u}// 情况三：在有向图里找到删除的那条边，使其变成树vector<int> getRemoveEdge(const vector<vector<int>>& edges) {init(); // 初始化并查集for (int i = 0; i < n; i++) { // 遍历所有的边if (isSame(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边return edges[i];}join(edges[i][0], edges[i][1]);}return {};}// 删一条边之后判断是不是树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;}join(edges[i][0], edges[i][1]);}return true;}
public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int inDegree[N] = { 0 }; // 记录节点入度n = edges.size(); // 边的数量for (int i = 0; i < n; i++) {inDegree[edges[i][1]]++; // 统计入度}vector<int> vec; // 记录入度为2的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {vec.push_back(i);}}// 情况一和情况二：如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树if (vec.size() > 0) {if (isTreeAfterRemoveEdge(edges, vec[0])) {return edges[vec[0]];}else {return edges[vec[1]];}}// 情况三：明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了return getRemoveEdge(edges);}
};int main() {//   // 684、冗余连接I-并查集-测试案例//vector<vector<int>> edges = { {1, 2}, {1, 3}, {2, 3} };//Solution s1;//vector<int> result = s1.findRedundantConnection(edges);// 685、冗余连接II-并查集-测试案例vector<vector<int>> edges = { {1, 2}, {1, 3}, {2, 3} };Solution2 s2;vector<int> result = s2.findRedundantDirectedConnection(edges);for (vector<int>::iterator it = result.begin(); it < result.end(); it++) {cout << *it << ' ';}cout << endl;system("pause");return 0;
}