The following algorithm returns the number of ultimate sinks in time O(n) where n is the number of vertices. Implement the it in a C# program, i.e. implement the function in a class and provide a Main() method that prints the output.

def find-possible-sink(vertices): if there's only one vertex, return it good-vertices := empty-set pair vertices into at most n/2 pairs add any left-over vertex to good-vertices for each pair (v,w): if v -> w: add w to good-vertices else: add v to good-vertices return find-possible-sink(good-vertices)

def find-sink(vertices): v := find-possible-sink(vertices) if v is actually a sink, return it return "there is no spoon^H^H^H^Hink"