disjointgraphs.scala

/**
 * SCALA!!
 */
object DisjointGraphs extends App {

  val disjoints = findThem(List((1,2), (2,3), (5,6), (7,8), (1,8)))
  println(disjoints)

  def findThem(edges: List[(Int, Int)]) = {
    val initial = List[Set[Int]]() // empty list of int sets
    edges.foldLeft(initial)((sets, nextEdge) =>
      sets.partition(s => s(nextEdge._1) || s(nextEdge._2)) match {
        case (Nil, rest) => Set(nextEdge._1, nextEdge._2) :: rest
        case (List(s1, s2), rest) => s1.union(s2) :: rest
        case (List(s1), rest) => s1 + nextEdge._1 + nextEdge._2 :: rest
    })
  }
}

awesome use of foldLeft and partition !