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

Question

给定n个人坐在桌旁，其中一些人彼此熟悉，熟悉度是双向关系，求最少要从桌子上淘汰的人，才能有一张桌子上每个人都熟悉的桌子邻居。给出 O(n^2) 的解

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

标签： algorithm

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]);
}