test.rb

require 'singleton'

class Question
  include Singleton
  include Enumerable

  attr_accessor :answer, :question

  def initialize
    @statement = [
      {
        q: [
          '8',
          'B depends on A',
          'C depends on B',
          'C depends on E',
          'D depends on C',
          'D depends on F',
          'E depends on A',
          'F depends on E',
          'G depends on F',
          'B F',
        ],
        a: 'B C D F G',
      },
      {
        q: [
          '3',
          '2 1',
          'B depends on A',
          'C depends on B',
          'B',

        ],
        a: 'B C'
      },
      {
        q: [
          '5 2',
          'P depends on Q',
          'P depends on S',
          'Q depends on R',
          'R depends on T',
          'S depends on T',
          'Q S',
        ],
        a: 'P Q S',
      },
      {
        q: [
          '8 2',
          'B depends on A',
          'C depends on B',
          'C depends on E',
          'D depends on C',
          'D depends on F',
          'E depends on A',
          'F depends on E',
          'G depends on F',
          'B F',
        ],
        a: 'B C D F G',
      }
    ]
  end

  def each(&block)
    until @statement.empty?
      build_question
      self.instance_exec(@answer, &block)
    end
  end

  def gets
    build_question unless @question && @answer
    @question.shift
  end

  def build_question
    @question, @answer = @statement.shift.values_at(:q, :a)
  end

  module STDIN
    def self.gets
      Question.instance.gets
    end
  end
  $stdin = STDIN
end

module Treerable
  include Enumerable

  attr_accessor :parent, :key

  def each(&block)
    children.each &block
  end

  def find_node(project_name)
    self.each do |node|
      return node if node.key == project_name

      target = node.find_node(project_name)
      return target if target
    end

    nil
  end

  def make_node(key, depends_on = nil)
    parent_node = find_node(depends_on) || Node.new(depends_on)
    child_node = (find_node(key) || Node.new(key))
    parent_node << child_node

    [parent_node, child_node].each do |node|
      self << node if node.parent.empty?
    end
  end

  def <<(node)
    if node.is_a?(Node)
      node.parent << self if node.parent
      children << node
    else
      new_node = Node.new(node, self)
      children << new_node
    end
  end

  def children
    @children ||= []
  end

  def parent
    @parent ||= []
  end
end

class Node
  include Treerable

  def initialize(key, parent_node = nil)
    @key = key
    parent << parent_node if parent_node
    @accident = false
  end

  def accidented_nodes
    if accident?
      [self] + self.children
    else
      self.children.map { |v| v.accidented_nodes }.flatten
    end
  end

  def accident!
    @accident = true
  end

  def accident?
    !!@accident
  end
end

class Tree
  include Treerable

  def accidents!(*project_names)
    project_names.each do |name|
      if node = find_node(name)
        node.accident!
      end
    end
  end

  def extent_of_the_impact
    self.map do |node|
      node.accidented_nodes
    end.flatten
  end

  def parent
    nil
  end
end

class Solver
  def initialize
    @tree = Tree.new

    gets.chomp.to_i.times do |i|
      /(?<var1>.) depends on (?<var2>.)/ =~ gets.chomp
      @tree.make_node(var1, var2)
    end
  end

  def solve
    @tree.accidents!(*gets.chomp.split(' '))
    @tree.extent_of_the_impact.map { |v| v.key }.uniq.sort
  end
end

if Object.const_defined?(:Question)
  Question.instance.each do |expected|
    puts Solver.new.solve == expected.split(' ')
  end
else
  puts Solver.new.solve
end