C++에서 가중치 경로가 있는 그래프에서 참인 쿼리 수를 계산하는 프로그램

각 모서리에 [u, v, w] 필드가 있고 u 및 v가 소스 및 대상 정점이고 w가 가중치인 무방향 그래프에 대한 모서리 목록이 있다고 가정합니다. 또한 [u, v, w]와 같은 형식의 쿼리 목록이 있습니다. 이는 경로의 각 모서리가 최대 w의 가중치를 갖도록 u와 v 사이에 경로가 존재하는지에 대한 질문을 나타냅니다. 따라서 참인 쿼리의 수를 찾으십시오.

따라서 입력이 edge =[[0, 1, 6],[1, 2, 7],[2, 3, 8],[0, 3, 5]] 같은 경우 쿼리 =[[0, 2, 14],[1,0,3]]

그러면 가중치가 13인 이 경로 [0, 1, 2]를 따라 노드 0에서 2로 이동할 수 있으므로 출력은 1이 됩니다. 그러나 에지 가중치 3을 사용하여 1에서 0으로 가는 경로는 없습니다.

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

• get_parent() 함수를 정의하면 x, 배열 par가 필요합니다.
• par[x]가 x가 아니면
  • par[x] :=get_parent(par[x], par)
• 반환 매개변수[x]
• 메인 방법에서 다음을 수행하십시오 -
• 1개의 2D 배열 gr 정의
• n :=0
• 에지의 각 에지 t에 대해 −
  • n :=n, t[0] 및 t[1]의 최대값
  • gr에 [t[2], 0, t[0], t[1]] 행 삽입
• 쿼리의 각 쿼리 t에 대해 −
  • gr에 [t[2], 1, t[0], t[1]] 행 삽입
• gr 정렬
• 크기가 n + 1인 배열 par를 정의하고 -1로 채움
• 초기화 i:=0의 경우, i <=n일 때 업데이트(i를 1만큼 증가), 수행 -
  • par[i] :=나
• sz :=쿼리 크기
• ans :=0
• gr
  의 각 행 t에 대해
  • a :=t[2], b :=t[3], tp :=t[1], d :=t[0]
  • px :=get_parent(a, par)
  • py :=get_parent(b, par)
  • tp가 0과 같으면 -
    • px가 py와 같지 않으면 -
      • par[py] :=px
  • 그렇지 않으면
    • px가 py와 같으면 -
      • (1만큼 증가)
    • (sz를 1 감소)
    • sz가 0과 같으면 -
      • 루프에서 빠져나오기
• 반환

예시(C++)

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

#include <bits/stdc++.h>
using namespace std;
int get_parent(int x, vector<int>& par) {
   if (par[x] != x) {
      par[x] = get_parent(par[x], par);
   }
   return par[x];
}
int solve(vector<vector<int>>& edges, vector<vector<int>>& queries) {
   vector<vector<int>> gr;
   int n = 0;
   for (auto t : edges) {
      n = max(n, max(t[0], t[1]));
      gr.push_back({t[2], 0, t[0], t[1]});
   }
   for (auto t : queries) {
      gr.push_back({t[2], 1, t[0], t[1]});
   }
   sort(gr.begin(), gr.end());
   vector<int> par(n + 1, -1);
   for (int i = 0; i <= n; i++) {
      par[i] = i;
   }
   int sz = queries.size();
   int ans = 0;
   for (auto t : gr) {
      int a = t[2];
      int b = t[3];
      int tp = t[1];
      int d = t[0];
      int px = get_parent(a, par);
      int py = get_parent(b, par);
      if (tp == 0) {
         if (px != py) {
            par[py] = px;
         }
      }else {
         if (px == py) {
            ans++;
         }
         sz--;
         if(sz == 0) {
            break;
         }
      }
   }
   return ans;
}
int main(){
   vector<vector<int>> edges = {{0, 1, 6},{1, 2, 7},{2, 3, 8},{0, 3, 5}};
   vector<vector<int>> queries = {{0, 2, 14},{1, 0, 3}};
   cout << solve(edges, queries);
}

입력

{{0, 1, 6},{1, 2, 7},{2, 3, 8},{0, 3, 5}}, {{0, 2, 14},{1, 0, 3}}

출력

1