https://paiza.jp/poh/phantom_thief の解答

Kaito813.scala

import java.util.Scanner
import scala.collection.mutable.PriorityQueue

sealed trait NodeState
case object Free extends NodeState
case class Half(a: Int) extends NodeState
case class Full(a: Int, b: Int) extends NodeState


case class Point(x: Long, y: Long){
  private var state: NodeState = Free

  def distance(that: Point): Long =
    (x - that.x) * (x - that.x) + (y - that.y) * (y - that.y)

  def show: String = s"${x} ${y}"
  def printout(): Unit = println(this.show)

  def getState: NodeState = state
  def updateState(d: Int): Unit =
    state match {
      case Free => state = Half(d)
      case Half(a) => state = Full(a, d)
      case Full(_, _) => throw new Exception("already Full")
    }
}


// O(α(n)) << O(log(n))
// v は頂点数
class UnionFind(v: Int){
  // 根であれば *そのグループの要素数(負)* が、子であれば親の番号が入る。
  val uni = Array.fill(v)(-1)

  // 頂点 v の所属するグループを調べる
  def root(v: Int): Int =
    uni(v) < 0 match{
      case true  =>  // v が親の場合
        return v
      case false =>  // v が子の場合
        uni(v) = root(uni(v))  // 親のrootを調べる
        return uni(v)
    }

  // 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
  def connect(a: Int, b: Int): Boolean = {
    // まずはそれぞれ根の番号に置き換える
    var ra = root(a)
    var rb = root(b)
    if(ra == rb)
      return false  // a と b がそもそも同じグループに属しているなら即終了

    // ra を大きなグループにしたいので、逆であれば入れ替える
    if(uni(ra) > uni(rb)) {  // rbの方が要素数が多ければ
      var tmp = ra
      ra = rb
      rb = tmp
    }

    // ra と rb を結合し、rb の親を ra とする
    uni(ra) += uni(rb)
    uni(rb) = ra
    return true
  }

  // 頂点 a, b が同じグループであるかを調べる
  def isConnect(a: Int, b: Int): Boolean =
    root(a) == root(b)

  // 頂点 a を含むグループの頂点数を調べる
  def size(a: Int): Int = -uni(root(a))
}


object Main extends App {
  val sc = new Scanner(System.in)
  val n = sc.nextInt()

  val points = new Array[Point](n)
  //                         (dist, (node1, node2))
  val pq = new PriorityQueue[(Long, (Int, Int))]
  

  for(i <- 0 until n){
    val x = sc.nextInt(); val y = sc.nextLong()
    points(i) = Point(x, y)
  }


  // process
  val uf = new UnionFind(n)
  val distanceMap = Array.ofDim[Long](n, n)
  for(i <- 0 until n-1; j <- i+1 until n){
    val dist = points(i).distance(points(j))
    
    distanceMap(i)(j) = dist
    distanceMap(j)(i) = dist

    pq.enqueue((-dist, (i, j)))
  }

  while(!pq.isEmpty){
    val (_, (a, b)) = pq.dequeue
    val posa = points(a); val posb = points(b)

    (posa.getState, posb.getState) match{
      case (Full(_, _), _) | (_, Full(_, _)) => ()
      case _ =>
        if(!uf.isConnect(a, b)){
          uf.connect(a, b)
          points(a).updateState(b); points(b).updateState(a)
        }
    }
  }


  def printAns(next: Int, pre: Int): Unit = {
    val nowpos = points(next)
    nowpos.getState match {
      case Free => throw new Exception("there are some wrong pre-process")
      case Half(_) => nowpos.printout()
      case Full(a, b) =>
        nowpos.printout()
        if(pre != a)
          printAns(a, next)
        else
          printAns(b, next)
    }
  }

  var ind = -1
  var flag = true
  while(flag){
    ind += 1
    points(ind).getState match {
      case Half(next) =>
        flag = false
        points(ind).printout()
        printAns(next, ind)
      case _ => ()
    }
  }
}