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
    })
  }
}

The real magic in here is partition. It returns 2 lists, one which the condition return true, the other where it returned false.

There's 3 possible return values for the call to partition.

• Neither node from this edge is in our list of graphs yet: the new list of graphs is the old one plus one with only the nodes from this edge.
• Exactly one graph from the list had one or both of the nodes in it. In which case, add both nodes to that graph (adding an element that's already there is ok because we're using a set) and then return the list with that new graph and the other graphs as they were
• One graph had one node, another graph had the other node. Merge these graphs and return a new list of graphs with these guys merged.

Not an efficient solution, but at least elegant.

awesome use of foldLeft and partition !