問題タブ [n-ary-tree]

ノード/頂点のリストと、これらのノードを接続するライン/エッジのリストがあります。リストはソートまたは順序付けされていませんが、特定のデータ セットのすべてのエッジとノードが含まれています。

エッジはデカルト座標 (x1,y1) および (x2,y2) で定義される線分であり、各ノードの位置も (x,y) 形式の座標で表されます。添付の画像は典型的なテスト ケースを示しており、ルート R1 と R2 を持つ 2 つのツリーを明確に示しています。リーフ ノード (Lx とラベル付けされ、オレンジ色のテキストと青色の円が強調表示されています) を含む各ノードは、対応する座標と共に示されています。

そして、各エッジは次のように表されます。

添付の画像から、エッジ N1-N2 が p1= (0,0)、p2=(20,20) または p1 =(20,20)、p2 = (0,0) として表されることは明らかです。順番はランダムです。

仮定 1: ノード R1 と R2 は、それらのノードのタイプから、ルート ノードとして明確に認識できます。(赤い外側の円と同心円)。仮定 2: ノードに直接接続されているすべてのエッジのリストも利用できます。たとえば、ノード N8 には、N8-L7、N8-R2、N8-N9、N8-N7 のセグメントがあります。

私の質問は、エッジのリストとノードのリストの 2 つの入力を持ち、ルート ノード、または子ノードを参照してツリーのルート ノードを返す関数を C# でどのように記述すればよいかということです。添付の図面に描かれているものに忠実です。

各ノードのエッジを一覧表示できましたが、ツリーを構築する方法がわかりません。クラスカルのアルゴリズムについて読んだことがありますが、この問題に適応できるかどうかはわかりません。図に示されている順序が維持されるかどうかはわかりません。

すべてのコードは C# ですが、C スタイルの言語ソリューションであれば何でも構いません。

注: この Web サイトで見た回答は、親ノードと子に関するツリー ノードの順序が既にわかっていることを前提としています。2 つのノードがエッジで接続されていることはわかりますが、どちらのノードが親ノードでどちらが子ノードであるかを判断できません。

ありがとうございました、

グレッグ・M

問題には q 個のクエリがあります。各クエリでは、ツリー全体でランダムなノードが与えられます。ツリーの各ノードには整数値が格納されます。ソルバーは、指定されたノードをルートとするサブツリー内の任意の 2 つのノードの任意の 2 つの数値の積の後に続くゼロの最小数を指定する必要があります。

すべてのノードに 2 と 5 の倍数を格納し、ボトムアップ方式ですべてのノードのゼロの最小数を計算することを考えました。