Блог

Я написал этот код для https://leetcode.com/problems/is-graph-bipartite/Это работает, но я думаю, что код ужасен. Проблемы:

1. Как мне сделать перерыв, когда я нахожу isBipartite= false
2. Как мне использовать только dfs (найти, является ли граф двудольным) для g.ключи, которые не были указаны. (когда есть 2 графика, не связанных друг с другом)

 import scala.collection.immutable.Queue
case class Step(q: Queue[Int]=Queue(),visited: List[Int]=List(),colors: List[Int]=List(),isBipartite: Boolean = true)
object Solution {
    def isBipartite(graph: Array[Array[Int]]): Boolean = {
        val g= graph.foldLeft(Map[Int,List[Int]]())((mp,arr)=>{
            val i= graph.indexOf(arr)
             if(arr.isEmpty){
                 mp   (i->List())
}else
            arr.foldLeft(mp)((m,v)=>{
                m   (i->(m.getOrElse(i,Nil) :  v))
            })
        })
        //println(g)
        val colors = List.fill(graph.size)(-1)
        //println(colors)
        g.keys.foldLeft(Step())((s,k)=>{
                if(!s.visited.contains(k) || s.isBipartite==true)
                bfs(k,g,s.copy(q=Queue(k),visited=(s.visited:  k),colors=colors.updated(k,1)))
            else
                s.copy(isBipartite=false)
        
        }).isBipartite
    }
    
    
    def bfs(start: Int, g: Map[Int,List[Int]], step1: Step): Step = {
        
    val s=Stream.iterate(step1) {
      case (step) =>
        
        //dequeue
        val (vertex, rest)=step.q.dequeue
        val newS=g.getOrElse(vertex,Nil).foldLeft(step)((s,v)=>{
            //println("vertex color for vertex " vertex " " s.colors(vertex))
             //println("v color " s.colors(v))
            if(s.colors(vertex)==s.colors(v)){
                //println("is not bipartite")
                 step.copy(isBipartite=false)
            }else if(s.colors(v) == -1){
                 //println(s.colors)
                 s.copy(colors=s.colors.updated(v,(1-s.colors(vertex))))    
            }else{
                 s
            }                                       
        })
        //add neighbours to queue
       val newQueue=rest.enqueue(g.getOrElse(vertex,Nil).filterNot(newS.visited.contains))    
        //mark neighbours visited
       val newVisited: List[Int] = newS.visited    g.getOrElse(vertex,Nil)
            
        newS.copy(q=newQueue,visited=newVisited)
    }.takeWhile(t=> t.q.nonEmpty).filterNot(n=>n.isBipartite).headOption
       if(!s.isEmpty)
            s.get
        else
            Step()
   
  }
    
}
  

Я придумал немного лучшее решение

 import scala.collection.immutable.Queue
case class Step(q: Queue[Int]=Queue(),colors: List[Int]=List(),isBipartite: Boolean = true)
object Solution {
    def isBipartite(graph: Array[Array[Int]]): Boolean = {
        //create a g
        val g= graph.foldLeft(Map[Int,List[Int]]())((mp,arr)=>{
            val i= graph.indexOf(arr)
             if(arr.isEmpty) mp   (i->List())
            else arr.foldLeft(mp)((m,v)=>m   (i->(m.getOrElse(i,Nil) :  v)))
        })
        
        //init colors array
        val colors = List.fill(graph.size)(-1)
        
        //iterate over all g keys which are not processed
        g.keys.foldLeft(Step(Queue(),colors,true))((s,k)=>
                if(s.colors(k) == -1 || s.isBipartite==true){
                    bfs(k,g,s.copy(q=Queue(k),colors=s.colors.updated(k,1)))
                } else s
        ).isBipartite
    }
    
    //color of neighbors should be opposite of vertex to be bipartite
    def bfs(start: Int, g: Map[Int,List[Int]], step: Step): Step = {
        Stream.iterate(step) {
            case (step) =>
            val (vertex, rest)=step.q.dequeue
            g.getOrElse(vertex,Nil).foldLeft(step.copy(q=rest))((s,v)=>{
            if(!s.isBipartite)  s
            else if(s.colors(vertex)==s.colors(v)) s.copy(isBipartite=false)            
else if(s.colors(v) == -1) s.copy(q=s.q.enqueue(v),colors=s.colors.updated(v,(1-s.colors(vertex))))    
            else s                                      
        })  
    }.takeWhile(t=> t.q.nonEmpty).last
  }
    
}