C++의 중복 연결 II

뿌리를 내린 나무가 있다고 가정해 봅시다. 이것은 다른 모든 노드가 이 노드의 자손인 정확히 하나의 노드(루트)가 있고 모든 노드는 루트 노드를 제외하고 정확히 하나의 부모를 갖는 방향 그래프입니다. 루트에는 부모가 없습니다.

주어진 입력에서 하나의 추가 방향 모서리가 추가된 N 노드(모든 값이 고유함)가 있는 루트 트리로 시작하는 방향 그래프. 추가된 가장자리는 1에서 N까지 선택된 두 개의 서로 다른 정점을 가지며 이미 존재하는 가장자리가 아닙니다.

그래프는 에지의 2D 배열입니다. 모서리의 각 요소는 노드 u와 v를 연결하는 방향 모서리를 나타내는 [u, v]와 같은 쌍입니다. 여기서 u는 자식 v의 부모입니다.

결과 그래프가 N 노드의 루트 트리가 되도록 제거할 수 있는 간선을 찾아야 합니다. 여러 답변이 있을 수 있으므로 주어진 2D 배열에서 마지막에 발생한 답변을 반환해야 합니다.

따라서 입력이 다음과 같으면 -

출력은 [2,3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• getParent() 함수를 정의하면 노드, 배열 부모가 사용됩니다.
• 부모[노드]가 -1과 같으면 -
  • 반환 노드
• 상위[노드] 반환 =getParent(상위[노드], 상위)
• 메인 방법에서 다음을 수행하십시오. -
• n :=가장자리 크기
• 크기가 n + 5인 배열 부모를 정의하고 -1로 채웁니다.
• 크기가 n + 5인 배열 ds를 정의하고 -1로 채웁니다.
• 마지막 :=-1, 두 번째 :=- 1, 첫 번째 :=- 1
• 초기화 i의 경우:=0, i
• u :=가장자리[i, 0], v :=가장자리[i, 1]
• 부모[v]가 -1과 같지 않으면 -
  • 첫 번째 :=부모[v]
  • 초 :=나
  • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
• 부모[v] :=나, 부모U :=getParent(u, ds), parentV :=getParent(v, ds)
• parentU가 parentV와 같으면 -
  • 마지막 :=나
• 그렇지 않으면,
  • ds[parentV] :=parentU

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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