algorithm - 使用拓扑顺序相互重叠的拾取棒

Question

我有一个算法任务，并且必须为这个问题编写一个伪代码，就像给定的一组 n 根棍子在某些配置中彼此重叠。具有 on 方法的类 Stick 使得对于 Sticks a 和 b，a.on(b) 恰好在 Stick a停留在b上时返回 true 。一根棍子只有在它上面没有棍子的情况下才能被挑选出来。我已经为它编写了以下伪代码，任何人都可以告诉我，如果我正在这样做的话……

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) 时间

Answer 1

首先形成一个数组 below[] 其中 below[i] = 棒号。即低于第 i 号棒（ i = 0 到 N-1 ）

for ( int i = 0; i < N; i++ ) {
  int stickBelow = -1;
  for ( int j = 0; j < N; j++ )
    if ( i.on( j ) {
      stickBelow = j;
      break;
    }
  below[i] = stickBelow;
}

现在遍历这个数组，并继续选择其 below[i] 是当前棒在顶部的棒。

int topStick = -1;
for ( int i = 0; i < N; i++ ) {
  for ( int j = 0; j < N; j++ ) {
    if ( below[j] == topStick ) {
      Choose the stick j;
      topStick = j;
      break;
    }
  }
}

上述算法的复杂度为 O(N^2)。