algorithm - 给定一个圆上的图的节点，找到要删除的最小节点数以得到一个图，其中每个节点都有到其下一个节点的边

Question

给定n个人坐在 table 旁，有些人彼此熟悉，熟悉度是双向关系，求从 table 上淘汰的最少人数，以得到 table 上的每个人都是熟悉它的邻居。给出 O(n^2) 的解

我目前的努力: 按照顺序，我尝试通过 T(n) = T(n-1) + O(n) 来解决问题， 但是如果我认为我已经找到了包含 m 个节点的理想圆，现在我想添加一个新节点，我检查新节点是否可以成为圆的新成员并创建 m+1 个节点的新圆，如果有可能问题就解决了，但如果没有，我确实需要存储所有长度为 m-1、m-2 的圆，...并将这个新节点添加到它们中，这需要超过 O(n)时间。

Answer 1

假设我们有一个 n 的图表节点，0 to n - 1 .

如果我们把问题看成寻找从节点A回到A的最短循环，节点a之间的距离和 b绝对不同(b - a - 1) (这是这两者之间的所有节点)我们只能从 a 开始至 b如果b > a或 a是起始节点。这个问题简化为寻找图中最短路径的经典问题。

使用 Dijkstra 算法，我们可以获得 O(N^2 log N) 算法。

Java代码:

class State{
    int node, distance;
}
int result = n - 1;
for(int i = 0; i < n; i++){
    //Find the shortest path to move from i -> i
    PriorityQueue<State> q = new PriorityQueue<>((a , b) -> Integer.compare(a.distance, b.distance));
    for(int j : map[i]) {
        if( j > i){
            q.add(new State(j , j - i + 1);
        }
    }  

    int[]dist = new int[n];
    Arrays.fill(dist, n - 1);
    while(!q.isEmpty()){
          State s = q.poll();
          if(s.distance != dist[s.node]){
               continue;
          }
          for(int j : map[s.node]){
               if((j > s.node || j == i) && dist[j] > s.distance + (j - s.node + 1)){
                    dist[j] = s.distance + (j - s.node + 1);
                    q.add(new State(j, dist[j]);
               }
          }
    }
    result = Integer.min(result, dist[i]);
}