Diamond.scala

package codejam

import scala.io.Source
import scala.collection.mutable.ListBuffer
import java.io.PrintWriter

object Diamond {

  val in = Source.fromFile("large.in").getLines
  val out = new PrintWriter("large.out")

  case class TestCase(klss: List[Klass]) {
    
    
    
    def solve: Boolean = {
      for {
        k <- klss
      } yield {
        var ps = k.getAllParents(this)
        if (ps.size != ps.toSet.size) return false
      }
      return true
    }
  }
  
  var cache = Map[List[Klass], List[Int]]()

  case class Klass(n: Int, parents: List[Int]) {

    def getAllParents(testCase: TestCase): List[Int] = {
      if(cache contains testCase.klss) {
        return cache(testCase.klss)
      }
      var thisParent = ListBuffer[Int]()
      for {
        klsIdx <- parents
      } {
        thisParent :+= klsIdx
        val kls = testCase.klss(klsIdx - 1)
        thisParent ++= kls.getAllParents(testCase)
      }
      cache += (testCase.klss -> thisParent.toList)
      thisParent.toList
    }
  }

  def toKlass(lines: List[String]): TestCase = {
    val klasses = for {
      i <- 0 until lines.size
    } yield Klass(i + 1, lines(i).split(" ").tail.map(_.toInt).toList)
    TestCase(klasses.toList)
  }

  def main(args: Array[String]) {
    val nOfCases = in.next.toInt
    val testCases = for {
      i <- 1 to nOfCases
      val nOfLines = in.next.toInt
      val strs = in.take(nOfLines).toList
    } yield {
      println(i + ", " + nOfLines)
      val res = if (toKlass(strs).solve) "Yes" else "No"
      s""" Case #$i: $res"""
      cache = cache.empty
    }

    testCases foreach out.println
    out.flush
  }

}