有向グラフ G = (V, E) の 2 乗はグラフ G2 = (V, E2) であり、u → w が E2 に含まれるのは、u ≠ w であり、両方の u→v を満たす頂点 v がある場合に限ります。そして v→w は E2 にあります。入力ファイルは、頂点の順序付けられたペアとして任意の順序でエッジを単純にリストし、各エッジは別の行に表示されます。頂点には、1 から頂点の総数まで順番に番号が付けられます。
*自己ループと重複/平行エッジは許可されていません
入力データの例を見ると:
1 6
1 4
1 3
2 4
2 8
2 6
2 5
3 5
3 2
3 6
4 7
4 5
4 6
4 8
5 1
5 8
5 7
6 3
6 4
7 5
7 4
7 6
8 1
出力は次のようになります。
1: 3 4 7 8 5 2 6
2: 5 6 3 4 1 8 7
3: 1 7 8 6 5 4
4: 5 6 8 7 3 1
5: 3 1 4 6
6: 2 7 5 8
7: 1 5 6 8 3 4
8: 6 4 3
Cでコードを書いています。
私の考えでは、ファイルを実行し、頂点の数を確認してから、ポインターの配列を割り当てます。行に 1 がある場所を探してリストをもう一度調べ、対応する番号がどこにつながるかを調べます。重複または同じ番号 (1) でない場合は、ポインターの配列からリンクされたリストに追加します。ファイル内の頂点番号ごとにこれを行います。
しかし、これは非常に非効率的であり、最善の方法ではないと思います。誰か他の提案があれば、私は非常に感謝しています。