0

私はアルゴリズムに割り当てがあり、いくつかの構成で互いの上に置かれている n 個のスティックの与えられたセットのような問題の疑似コードを書かなければなりません。スティック a および b に対して、 a.on(b) がスティックaがb上にあるときに正確に true を返す on メソッドを持つ Stick クラス。スティックは、スティックがない場合にのみ選択できます..次の疑似コードを書きました。

Begin 
 For each stick s(v) 
  Construct a vertex v for Graph G; 
 End For 

 if a.on(b) 
 Return True; 
 Else 
 Return False; 
 End If 

 TopologicalSort(G); 
 If cycle is found by TopologicalSort 
 Return No; 
 Else 
 Return the order of each stick produced by TopologicalSort; 
 End If 
End

このアルゴリズムの実行時間は O(n) 時間です

4

1 に答える 1