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, ]

更新于:2020年6月1日

176 次浏览

启动你的职业生涯

完成课程获得认证

开始
广告