C++中的冗余连接 II
假设我们有一棵有根树。这是一个有向图,只有一个节点(根节点),所有其他节点都是这个节点的后代,并且除根节点外,每个节点只有一个父节点。根节点没有父节点。
在给定的输入中,一个有向图,它最初是一个有N个节点的有根树(所有值都是唯一的),并添加了一条额外的有向边。添加的边是从1到N中选择的两个不同的顶点,并且不是已经存在的边。
图将是一个二维边的数组。边的每个元素都是一个类似于[u, v]的pair,表示连接节点u和v的有向边,其中u是子节点v的父节点。
我们必须找到一条可以移除的边,以便生成的图成为一个有N个节点的有根树。可能有多个答案,我们必须返回在给定二维数组中最后出现的答案。
因此,如果输入如下:
输出将是 [2,3]
为了解决这个问题,我们将遵循以下步骤:
- 定义一个函数 getParent(),它将接收节点和一个父节点数组。
- 如果 parent[node] 等于 -1,则:
- 返回 node
- 返回 parent[node] = getParent(parent[node], parent)
- 在主方法中,执行以下操作:
- n := edges 的大小
- 定义一个大小为 n + 5 的父节点数组,并将其填充为 -1
- 定义一个大小为 n + 5 的 ds 数组,并将其填充为 -1
- last := -1, second := -1, first := -1
- 对于初始化 i := 0,当 i < n 时,更新(i 增加 1),执行:
- u := edges[i, 0], v := edges[i, 1]
- 如果 parent[v] 不等于 -1,则:
- first := parent[v]
- second := i
- 忽略以下部分,跳到下一个迭代
- parent[v] := i, parentU := getParent(u, ds), parentV := getParent(v, ds)
- 如果 parentU 等于 parentV,则:
- last := i
- 否则:
- ds[parentV] := parentU
- 如果 last 等于 -1,则:
- 返回 edges[second]
- 如果 second 等于 -1,则:
- 返回 edges[last]
- 返回 edges[first]
让我们看看以下实现,以便更好地理解:
示例
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: int getParent(int node, vector <int>& parent){ if(parent[node] == -1)return node; return parent[node] = getParent(parent[node], parent); } vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) { int n = edges.size(); vector <int> parent(n + 5, -1); vector <int> ds(n + 5, -1); int last = -1, second = -1, first = -1; int u, v; int parentU, parentV; for(int i = 0; i < n; i++){ u = edges[i][0]; v = edges[i][1]; if(parent[v] != -1){ first = parent[v]; second = i; continue; } parent[v] = i; parentU = getParent(u, ds); parentV = getParent(v, ds); if(parentU == parentV){ last = i; }else ds[parentV] = parentU; } if(last == -1)return edges[second]; if(second == -1)return edges[last]; return edges[first]; } }; main(){ Solution ob; vector<vector<int>> v = {{1,2},{1,3},{2,3}}; print_vector(ob.findRedundantDirectedConnection(v)); }
输入
{{1,2},{1,3},{2,3}}
输出
[2, 3, ]
广告