Pythonでエッジ長が制限されたパスの存在をチェックするプログラム

1つのedgeListを使用するn個のノードを持つ1つの無向加重グラフがあるとします。ここで、edgeList [i]には3つのパラメーター（u、v、w）があり、距離がwのuからvへのパスがあることを示します。 query [i]が（p、q、lim）を持つ別のクエリ配列もあります。このクエリは、距離がlim未満のpからqへのパス（直接または他のノード経由）があるかどうかを尋ねようとしています。クエリごとにTrue/Falseの結果を保持する配列を返す必要があります。

したがって、入力が次のような場合

その場合、出力は[True、False、True]になります。 1から4に移動するには、コスト11でパス1-> 3-> 4をたどることができるため、3未満を使用して2から3に移動できないため、2番目のパスはfalseになり、1から移動できるため最後のパスはtrueになります。パス1->3->2を使用して2に変換します。コストは14で15未満です。

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

• 親：=0からnまでのリスト

• ランク：=サイズn+1のリストと0で埋める

• 関数find（）を定義します。これは親を取ります、x

• parent [x]がxと同じ場合、

  • xを返す

• parent [x]：=find（parent、parent [x]）

• 親を返す[x]

• 関数union（）を定義します。これは親、a、bを取ります

• a：=find（parent、a）

• b：=find（parent、b）

• aがbと同じ場合、

  • 戻る

• ランク[a]<ランク[b]の場合、

  • 親[a]：=b

• それ以外の場合、ランク[a]>ランク[b]の場合、

  • 親[b]：=a

• それ以外の場合

  • 親[b]：=a

  • ランク[a]：=ランク[a] + 1

• メインの方法から、次のようにします-

• 重みパラメータに基づいてedgeListを並べ替える

• res：=クエリの数と0で埋める配列

• クエリ：=クエリからの各インデックスiと値chのペア（i、ch）のリスト

• 制限パラメータに基づいてクエリを並べ替える

• ind：=0

• クエリ内のインデックスiトリプレット（a、b、w）ごとに、実行します

  • 一方、ind

    • union（parent、edgeList [ind、0]）

    • ind：=ind + 1

  • res [i]：=find（parent、a）はfind（parent、b）と同じです

• 解像度を返す

例

理解を深めるために、次の実装を見てみましょう

def solve(n, edgeList, queries):
   parent = [i for i in range(n+1)]

   rank = [0 for i in range(n+1)]

   def find(parent, x):

      if parent[x] == x:
         return x
      parent[x] = find(parent, parent[x])
      return parent[x]

   def union(parent, a, b):

      a = find(parent, a)
      b = find(parent, b)

      if a == b:
         return

      if rank[a] < rank[b]:
         parent[a] = b
      elif rank[a] > rank[b]:
         parent[b] = a
      else:
         parent[b] = a
         rank[a] += 1

   edgeList.sort(key = lambda x: x[2])
   res = [0] * len(queries)
   queries = [[i, ch] for i, ch in enumerate(queries)]
   queries.sort(key = lambda x: x[1][2])

   ind = 0
   for i, (a, b, w) in queries:

      while ind < len(edgeList) and edgeList[ind][2] < w:
         union(parent, edgeList[ind][0], edgeList[ind][1])
         ind += 1

      res[i] = find(parent, a) == find(parent, b)
   return res

n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3),]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries))

入力

4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)],[(1,4,12),(2,3,3),(1,2,15)]

出力

[True, False, True]