BFFs.scala

object BFFs extends App {

  def maxCircleSize(bffs0: IndexedSeq[Int]): Int = {
    val bffs = bffs0.map(_ - 1)

    @annotation.tailrec
    def findLoops(notVisited: Set[Int], visited: Set[Int], loops: List[Seq[Int]]): Seq[Seq[Int]] =
      if (notVisited.isEmpty) loops
      else {
        @annotation.tailrec
        def search(visiting: List[Int]): (Seq[Int], Option[Int]) = {
          val next = bffs(visiting.head)
          val indexWhere = visiting.indexWhere(_ == next)
          if (indexWhere > -1) (visiting, Some(indexWhere + 1))
          else if (visited contains next) (visiting, None)
          else search(next :: visiting)
        }
        val (visiting, loopSizeOption) = search(notVisited.head :: Nil)
        findLoops(
          notVisited -- visiting,
          visited ++ visiting,
          loopSizeOption map visiting.take map loops.:: getOrElse loops
        )
      }

    val loops = findLoops((0 until bffs.size).toSet, Set(), Nil)

    val g: Map[Int, Set[Int]] = bffs.zipWithIndex.groupBy(_._1).mapValues(_.map(_._2).toSet) withDefaultValue Set()

    def coupleClusterSize(couple: Seq[Int]): Int = {
      def height(index: Int): Int = (0 /: (g(index) -- couple map height))(_ max _) + 1
      (couple map height).sum
    }

    (loops.map(_.size) :+ (loops filter (_.size == 2) map coupleClusterSize).sum).max
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      lineIn.next()
      lineOut(s"Case #$i: ${maxCircleSize(lineIn.next().split(" ").map(_.toInt))}")
    }

  val filename = "C-large-practice"
  val writer = new java.io.PrintWriter(filename + ".out")
  try {
    process(io.Source.fromFile(filename + ".in").getLines) { s =>
      writer.println(s); writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }
}

BFFsTest.scala

import org.scalatest._

import BFFs._

class BFFsTest extends FunSuite with Matchers {

  test("sample #1") {
    assert(maxCircleSize(IndexedSeq(2, 3, 4, 1)) === 4)
  }

  test("sample #2") {
    assert(maxCircleSize(IndexedSeq(3, 3, 4, 1)) === 3)
  }

  test("sample #3") {
    assert(maxCircleSize(IndexedSeq(3, 3, 4, 3)) === 3)
  }

  test("sample #4") {
    assert(maxCircleSize(IndexedSeq(7, 8, 10, 10, 9, 2, 9, 6, 3, 3)) === 6)
  }

  test("case #5") {
    assert(maxCircleSize(IndexedSeq(2, 3, 1, 10, 3, 5, 6, 7, 8, 9)) === 3)
  }

  test("case #18") {
    assert(maxCircleSize(IndexedSeq(3, 4, 1, 3, 6, 1)) === 6)
  }

  test("case #28") {
    assert(maxCircleSize(IndexedSeq(2, 1, 4, 3, 6, 5)) === 6)
  }

  test("sample case") {
    val input = """4
4
2 3 4 1
4
3 3 4 1
4
3 3 4 3
10
7 8 10 10 9 2 9 6 3 3""".lines

    val expected = """Case #1: 4
Case #2: 3
Case #3: 3
Case #4: 6""".lines

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("C-small-practice.in").getLines()
    val expected = io.Source.fromFile("C-small-practice.out").getLines()

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("C-large-practice.in").getLines()
    val expected = io.Source.fromFile("C-large-practice.out").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]): Unit = {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}