第74天(中等题 数据结构)

打卡第七十四天
1道中等题

题目：

思路：并查集

代码：

class Solution {
public:vector<int> parent;  // 存储每个节点的父节点vector<int> findRedundantConnection(vector<vector<int>>& edges) {int n = edges.size();  // 边的数量parent.resize(n + 1);  // 从1开始，因为节点编号从1开始for(int i = 1; i <= n; i++) {parent[i] = i;  // 初始时每个节点自成一个集合}for(auto& edge : edges) {int x = edge[0], y = edge[1];  // 获取当前边的两个节点if(find(x) == find(y)) {// 如果两个节点已经在同一个集合中，说明这条边会形成环return edge;  // 返回这条冗余边} else {Union(x, y);  // 合并两个集合}}return {};  // 没有找到冗余边返回空向量}int find(int x) {if(x == parent[x]) {// 如果x是自己的父节点return x;  } else {return parent[x] = find(parent[x]);  // 将x的父节点直接设置为根节点}}void Union(int x, int y) {// 将两个节点所在的集合合并int rootx = find(x);  // 找到x的根节点int rooty = find(y);  // 找到y的根节点if(rootx != rooty) {// 如果两个节点不在同一个集合中if(rootx < rooty) {parent[rooty] = rootx;  // 将y的根节点指向x的根节点} else {parent[rootx] = rooty;  // 将x的根节点指向y的根节点}}}
};

耗时≈半小时 明天继续