[LeetCode] 882。細分化されたグラフの到達可能ノード細分化されたグラフの到達可能ノード
882 Reachable Nodes Subdivided Graph Reachable Nodes Subdivided Graph
0からのノードを持つ無向グラフ（「元のグラフ」）から始めます。 N-1に、いくつかのエッジに細分割が行われます。
グラフは次のように与えられます：edges[k]整数ペアのリストです(i, j, n)そのような(i, j)元のグラフのエッジです。
およびnそのエッジ上の新しいノードの総数です。
次に、エッジ(i, j)元のグラフから削除されますn新しいノード(x_1, x_2, ..., x_n)元のグラフに追加され、
およびn+1新しいエッジ(i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j)元のグラフに追加されます。
ここで、ノード0から開始します。元のグラフから、各移動で、1つのエッジに沿って移動します。
最大でM移動できるノードの数を返します。
例1：
Input: `edges` = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3 Output: 13 Explanation: The nodes that are reachable in the final graph after M = 6 moves are indicated below. 
例2：
Input: `edges` = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4 Output: 23注意：
0 <= edges.length <= 100000 <= edges[i][0] < edges[i][1] < Ni != jは存在しませんそのためにedges[i][0] == edges[j][0]およびedges[i][1] == edges[j][1]。- 元のグラフには平行なエッジがありません。
0 <= edges[i][2] <= 100000 <= M <= 10^91 <= N <= 3000- 到達可能なノードは、ノード0から開始して最大M回の移動を使用して移動できるノードです。
この質問は、N個のノードを含む無向グラフを示しますが、次のフェーズに到達したと仮定すると、各2つのノード間に多くの異なるノードが存在する可能性があります。隣接ノードは1ステップを消費する必要があります。これで、あとMステップあります。 Mステップで到達できるさまざまなノードの数を尋ねます。 N個の大きなノードがあり、中央に番号のない小さなノードがいくつかありますが、最終的には、ノードのサイズに関係なく、すべてが異なるノードとしてカウントされます。この質問をよりよく理解するために、実際には、N個の番号のノードは州都などのN個の大都市と見なすことができます。2つの州都の間に複数の小都市があります。隣の都市へ。これで、最大M便を利用して、州都0から出発した場合に到達できる都市の数を尋ねることができます。州都は大きなトランジットステーションであるため、さまざまな都市に行くには複数のオプションしかありません。 2つの州都の各小都市には2つの選択肢しかないため、この質問は実際には1つです。この種のグラフの走査は、毎回番号付きノードに到達することが保証されているわけではありません。番号が付けられたノードに到達した場合にのみ、トラバーサルを続行できます。番号が付けられたノードに到達すると、この時点での残りのステップ数も計算されます。つまり、前の番号が付けられたノードの残りのステップ数から、現在のパス上のすべての小さなノードの数を引いた数が使用されます。現在の残りのステップ数が次の大きなノードに到達するのに十分でない場合は、移動した小さなノードの数をマークする方法を見つける必要があります。そうでない場合は、次に別のパスを介して同じ次の大きなノードに到達するときに、Goingさらに戻って、小さなノードの数を数えることを繰り返すことが可能です。スモールノードにはラベルがないため、直接ラベルを付けることはできず、最も近いラージノードの数でのみマークを付けることができます。したがって、この質問は無向グラフですが、有向グラフとして扱う必要があります。たとえば、2つの大きなノードAとBを処理するには、中央に10個の小さなノードがあり、ノードAの時点で6つのステップしか実行できません。次に、中央に6つのノードを取得しました。 BがAの方向から始まる場合、4つの小さなノードのみが移動できます。
実際、ノードごとに（数値があるかどうかに関係なく）さらに分析するために、ノードと開始ノードの間の最短距離を計算でき、距離がM以下の場合、このノードは次のようになります。到達可能でなければなりません。このように、本質は単一のソースポイントの最短距離を見つけることです。このとき、アーティファクトのダイクストラアルゴリズムであるダイクストラアルゴリズムを犠牲にする必要があります。 LeetCodeでこのアルゴリズムを使用する際の問題もあります ネットワーク遅延時間 と 迷路II 。アルゴリズムの一般的な形式は、最小ヒープを使用して、ソースポイントまでの最小距離を節約することです。ここでは、ソースポイントまでの最小距離を直接カウントするのはあまり便利ではありません。小さなトリックを使用できます。つまり、最大ヒープを使用して現在のノードをカウントできます。残りの最大ステップ数。残りのステップが多いほど、ソースポイントからの距離が短くなるためです。ダイクストラアルゴリズムは開始点を中心としているため、終了点に到達するまで外層に拡張されます。この機能によると、BFSを使用して実装することをお勧めします。まず、隣接リンクリストを作成しましょう。ここでは、NxN 2次元配列グラフを使用できます。ここで、グラフ[i] [j]は、大きなノードiから大きなノードjまでを表します。方向が通過する小さなノードの数。隣接リストを作成するときは、エッジごとに両方向を割り当てる必要があります。上で説明したように、それは有向グラフとして行われるべきです。次に、最大ヒープを使用し、残りのステップとノード番号のペアの数をその中に入れ、残りのステップを前に置いて、デフォルトで大きいステップから小さいステップの数でソートし、初期化中に{M、0}を格納します最大のヒープ。また、ノードが訪問されたかどうかを記録するために、訪問された1次元配列が必要です。 whileループでは、最初にヒープの最上位要素のペアの数を取得し、移動するステップ数を取得し、現在のノード番号curを取得します。この時点で、ノードにアクセスしたかどうかを確認し、直接スキップします。それ以外の場合はスキップします。訪問した配列でマークされているのはtrueです。このとき、現在のラージノードも新たにトラバースされるため、結果resは1増加し、その数を累積する必要があります。次に、curに接続されているすべての大きなノードをトラバースする必要があります。 2次元配列の形式の隣接リストの場合、iを0からNまでトラバースするだけで済みます。グラフ[cur] [i]が-1の場合、ノードcurとノードiが接続されていないことを意味します。スキップしてください。それ以外の場合、2つのノードが接続されている場合、2つの大きなノード内の小さなノードの数はグラフ[cur] [i]になります。このとき、現在のcurノードの残りのステップ移動と比較する必要があります。移動が大きい場合は、ノードiに到達できることを意味します。 、この時点でノードiに到達するための残りのステップmove-graph [cur] [i] -1（最後のマイナス1はノードiに到達するために必要な追加のステップです）とiを組み合わせてペアの数を形成し、最大値を結合します以前の分析により、ノードcurがノードiに渡したすべてのノードは、ノードiからノードcurに移動できなくなります。そうしないと、重複ノードが蓄積されるため、グラフ[i] [cur] moveとgraph [cur] [i]で小さい方の値を引くと、結果resは小さい方の値を累積するはずです。次のコードを参照してください。
解決策1：解決策1：
class Solution { public: int reachableNodes(vector& edges, int M, int N) { int res = 0 vector graph(N, vector(N, -1)) vector visited(N) priority_queue pq pq.push({M, 0}) for (auto &edge : edges) { graph[edge[0]][edge[1]] = edge[2] graph[edge[1]][edge[0]] = edge[2] } while (!pq.empty()) { auto t= pq.top() pq.pop() int move = t.first, cur = t.second if (visited[cur]) continue visited[cur] = true ++res for (int i = 0 i graph[cur][i] && !visited[i]) { pq.push({move - graph[cur][i] - 1, i}) } graph[i][cur] -= min(move, graph[cur][i]) res += min(move, graph[cur][i]) } } return res } }
HashMapを使用して隣接リストを作成することもできます。最終的な実行速度は、2次元配列形式の隣接リストよりも高速です。他の場所は変更されていません。以下のコードを参照してください。
解決策2：解決策2：
class Solution { public: int reachableNodes(vector& edges, int M, int N) { int res = 0 unordered_map graph vector visited(N) priority_queue pq pq.push({M, 0}) for (auto &edge : edges) { graph[edge[0]][edge[1]] = edge[2] graph[edge[1]][edge[0]] = edge[2] } while (!pq.empty()) { auto t= pq.top() pq.pop() int move = t.first, cur = t.second if (visited[cur]) continue visited[cur] = true ++res for (auto &a : graph[cur]) { if (move > a.second && !visited[a.first]) { pq.push({move - a.second - 1, a.first}) } graph[a.first][cur] -= min(move, a.second) res += min(move, a.second) } } return res } }
Github同期アドレス：
https://github.com/grandyang/leetcode/issues/882
参考資料：
https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/
LeetCodeオールインワントピック説明の要約（継続的に更新しています...）
転載：https：//www.cnblogs.com/grandyang/p/11074953.html