BadHorse.scala

import java.io.{FileOutputStream, File, PrintWriter}
import scala.collection.mutable.ListBuffer
import scala.io.Source

object Main {

  def solve(input: List[(String, String)]): String = {
    val mans = (input.map(_._1) ::: input.map(_._2)).toSet
    // 사람 -> Set(싫어하는 사람 목록)
    val mapping = (input ::: input.map{case (k, v) => (v, k)}).groupBy(_._1).map({case (k, v) => (k, v.map(_._2).toSet)})

    // remains - 찾지 않은 사람들
    // teams - 배정된 팀들
    // nexts - 다음 처리할 사람들
    // nextTeam - 다음 팀 번호
    def getAnswer(remains:Set[String], teams: Map[String, Int], nexts:Set[String], nextTeam:Int):String = {
      println(s"remains:$remains, teams:$teams, nexts:$nexts, nextTeam:$nextTeam")
      if (remains.isEmpty && nexts.isEmpty) {
        "Yes"
      }
      else {
        if (nexts.isEmpty) { // 처리할 사람이 없는 경우
        val testPerson = remains.head
          getAnswer(remains.tail, teams + (testPerson -> 0), mapping(testPerson), 1)
        }
        else {
          // 배정된 팀과 다른 경우가 있는지 확인
          if (nexts.exists(teams.getOrElse(_, nextTeam) != nextTeam)) {
            "No"
          }
          else {
            getAnswer(remains diff nexts, teams ++ nexts.toList.map((_, nextTeam)), nexts.flatMap(mapping(_)).filter(x => remains.exists(_ == x)), (nextTeam + 1) % 2)
          }
        }
      }
    }
    getAnswer(mans, Map(), Set(), 0)
  }


  def main(args: Array[String]) {
    val lines = Source.fromFile("A-small-practice-2.in").getLines()
    val w = new PrintWriter(new FileOutputStream(new File("sample2.out")),true)
    val caseNum = lines.next().toInt
    1 to caseNum foreach {
      caseIndex => {
        val n = lines.next().toInt
        val lb = new ListBuffer[(String, String)]()
        (1 to n) foreach {m =>
          val Array(man1, man2) = lines.next().split(" ")
          lb += Tuple2(man1, man2)
        }

        val answer = solve(lb.toList)
        val output = s"Case #$caseIndex: $answer"
        println(output)
        w.println(s"Case #$caseIndex: $answer")
      }
    }
  }
}