算法设计，实现了一个有向图的算法

Question

我发现这个有趣的问题与算法设计有关，我不能正确地解决它。

给定一个使用邻接表的有向图G = (V,E)和一个整数k <，实现一个线性时间复杂度算法(O(n))，来检验图G是否至少有k个顶点具有相同的阶数。
假设n == |V| + |E|

Answer 1

通过所有边，甚至通过所有边in-nodes，并保持所有可能的度数的顶点数量就足够了。

python风格的方法草图:

def check(graph, k):
  # For each vertex count indegree
  indegrees = [0] * graph.number_of_nodes()
  # 'Maps' number of vertices to indegree
  num_with_indegree = [graph.number_of_nodes()] + [0] * (graph.number_of_nodes()-2)
  # Pass through all edge innodes.
  # This iteration is easy to implement with adjancency list graph implementation.
  for in_node in graph.in_nodes():
    # Increase indegree for a node
    indegrees[in_node] += 1
    # 'Move' vertex to it's indegree bucket
    indegree = indegrees[in_node]
    num_with_indegree[indegree-1] -= 1
    num_with_indegree[indegree] += 1
  # Returns true if any bucket has at least k vertices
  return any(n >= k for n in num_with_indegree)