C++の加重パスを持つグラフで真であるクエリの数をカウントするプログラム

無向グラフのエッジリストがあり、各エッジに[u、v、w]フィールドがあり、uとvがソース頂点と宛先頂点であり、wが重みであるとします。また、同じ形式[u、v、w]のクエリのリストもあります。これは、パスの各エッジの重みが最大でwになるようなuとvの間にパスが存在するかどうかという問題を表しています。したがって、真のクエリの数を見つけてください。

したがって、入力がエッジのような場合=[[0、1、6]、[1、2、7]、[2、3、8]、[0、3、5]]クエリ=[[0、2、 14]、[1、0、3]]

この場合、出力は1になります。これは、重み13でこのパス[0、1、2]をたどることでノード0から2に移動できるためです。ただし、エッジの重み3で1から0へのパスはありません。

これを解決するには、次の手順に従います-

• 関数get_parent（）を定義します。これには、配列パラメーターであるxが必要です。
• par [x]がxでない場合、
  • par [x]：=get_parent（par [x]、par）
• return par [x]
• メインの方法から次のようにします-
• 1つの2D配列grを定義する
• n：=0
• エッジの各エッジtについて-
  • n：=最大n、t[0]およびt[1]
  • 行[t[2]、0、t [0]、t[1]]をgrに挿入します
• クエリ内のクエリtごと-
  • 行[t[2]、1、t [0]、t[1]]をgrに挿入します
• ソートgr
• サイズn+1の配列パーを定義し、-1で埋めます
• iを初期化する場合：=0、i <=nの場合、更新（iを1つ増やす）、実行-
  • par [i]：=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と同じ場合、-
      • （ansを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