算法设计，实现有向图的算法

Question

我发现了这个与算法设计相关的有趣问题，我无法正确解决它。

Given a directed graph G = (V,E), which uses adjancency lists, and an integer k < |V|, implement a linear-time-complexity algorithm ( O(n) ) , to check if the graph G has at least k vertexes with the same indegree number.
Suppose n == |V| + |E|

Answer 1

遍历所有边，甚至遍历所有边内节点，并保持所有可能入度的顶点数就足够了。

pyhon风格的方法草图：

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)

算法设计，实现有向图的算法

Algorithm design, implement an algorithm for a directed graph

algorithm

graph-theory