隣接グラフといくつかのトラバーサルが与えられたときに、最もトラバースされたエッジを見つける方法を最適化する

Question

ツリーのN個の頂点と、対応する隣接グラフをN×Nの配列adjGraph[N][N]として表します。たとえば、（1,3）がエッジの場合は、adjGraph[0][2] == 1です。それ以外の場合は、エッジではない（i、j）sのadjGraph[i][j] == 0です。

Iがの形で一連の入力を与えられてい

：パスは頂点5に頂点1から開始トラバースされたことを示す

1 5 

私はtravesedたエッジを見つけることを希望ほとんどの時間、それが横断された回数と一緒に。これを行うために、別のN行N配列numPass[N][N]を持っています。その要素は最初に0に初期化され、インデックスに一致するエッジを含むパスが特定されるたびに1ずつ増加します。たとえば、パス（2,4）にエッジ（2,3）と（3,4）が含まれている場合は、numPass[1][2]とnumPass[2][3]を1ずつ増やします。

私が理解しているように、入力には開始頂点と終了頂点の情報しか与えられておらず、どちらのエッジが2つのエッジを結ぶかはわかります。与えられたグラフはツリーなので、2つの頂点間のパスは一意です。したがって、入力パスの終点のインデックスが与えられていると、どのエッジが接続されているかを再帰的に逆追跡できると仮定しました。

次は私が念頭に置いて、そのアイデアを実現しようとした機能コードです：

// find the (unique) path of edges from vertices x to y 
// and increment edges crossed during such a path 
void findPath(int x, int y, int N, int adjGraph[][N], int numPass[][N]) { 
int temp; 

// if the path is a single edge, case is trivial 
if (adjGraph[x][y] == 1) { 
    numPass[x][y] += 1; 
    return; 
} 

// otherwise, find path by backtracking from y 
backtrack: while (1) { 
    temp = y-1; 
    if (adjGraph[temp][y] == 1) { 
     numPass[temp][y] += 1; 
     break; 
    } 
} 
if (adjGraph[x][temp] == 1) { 
    numPass[x][temp] += 1; 
    return; 
} else { 
    y = temp; 
    goto backtrack; 
} 

はしかし、問題は、私のコードは、小さな入力に対して正常に動作している間、それはのためにメモリを使い果たしていることです私は128MBのメモリ制限と1秒の制限があります。入力の範囲は最大222222の頂点と222222の入力パスです。

このような大きな入力を満たすためにメソッドを最適化するにはどうすればよいですか？

Answer 1

1. 隣接行列を削除します（O(N^2)スペースを使用）。代わりに隣接リストを使用してください。

2. より効率的なアルゴリズムを使用してください。木を根づかせましょう。 aからbまでのパスについては、aとbに1を加え、lcaから1を減算することができます（この方法では、このパス上のエッジにのみ追加されます）。

3. すべてのパスを処理した後、エッジを通過するパスの数はサブツリー内の単なる合計にすぎません。

我々はLCAを計算するために効率的なアルゴリズムを使用している場合は、このソリューションがQは、パスの数であるO(N + Q * log N)、で動作します。この制約のために十分に見えます（lcaを見つけるためのより複雑でより効率的なアルゴリズムを使用することで、実際にはもっとうまくいくことができますが、ここでは必要ないと思います）。

注：lcaは、最低共通祖先を意味します。