package Ġalgorithm Ċ Ċ import Ġgraphs . Ad jacency Matrix Graph Ċ import Ġgraphs . Graph Ċ import Ġmu . Kotlin Logging Ċ import Ġjava . util .* Ċ import Ġkotlin . math . ceil Ċ import Ġkotlin . math . max Ċ import Ġkotlin . math . min Ċ import Ġkotlin . properties . Deleg ates Ċ Ċ private Ġval Ġlogger Ġ= ĠKotlin Logging . logger Ġ{} Ċ Ċ /** Ċ Ġ* ĠÐľ Ð½ Ð¾Ð¶ ÐµÑģÑĤÐ²Ð¾ ĠÐ²ÑģÐµ Ñħ ĠÐ¾ ÑģÑĤ Ð¾Ð² Ð½ÑĭÑħ ĠÐ¿Ð¾Ð´ Ð³ ÑĢÐ° ÑĦ Ð¾Ð² ĠÐ·Ð°Ð´ Ð°Ð½ Ð½Ð¾Ð¹ Ġk - Ñģ Ð² ÑıÐ· Ð½Ð¾ÑģÑĤÐ¸ . Ċ Ġ* ĠÐ ¥ ÑĢÐ°Ð½ Ð¸ÑĤ ÑģÑı ĠÐ¸ Ñģ ÑħÐ¾Ð´ Ð½ÑĭÐ¹ ĠÐ³ ÑĢÐ° ÑĦ Ġ+ ĠÑģÐ¿Ð¸Ñģ Ð¾Ðº ĠÐ½ ÐµÐ¿ ÑĢ Ð¾Ð¹ Ð´ ÐµÐ½ Ð½ÑĭÑħ ĠÑĢ Ñĳ Ð± ÐµÑĢ Ċ Ġ* Ġ( ÑĢ Ñĳ Ð± ÑĢÐ° ĠÐ½Ðµ ĠÐ² ÑħÐ¾Ð´ Ñı ÑīÐ¸Ðµ ĠÐ² ĠÑģÐ¿Ð¸Ñģ Ð¾Ðº ĠÑģ Ñĩ Ð¸ÑĤ Ð° ÑİÑĤÑģÑı ĠÑĦ Ð¸Ðº Ñģ Ð¸ÑĢÐ¾Ð² Ð°Ð½ Ð½Ñĭ Ð¼Ð¸ ĠÐ¾ÑĤ ĠÑĥ Ð´Ð°Ð» ÐµÐ½Ð¸Ñı ). Ċ Ġ*/ Ċ class ĠSub graph ( ĊĠĠĠ Ġval Ġgraph : ĠGraph , ĊĠĠĠ Ġval Ġraw Edges : ĠMutable List < Pair < Int , ĠInt >>, ĊĠĠĠ Ġval Ġk : ĠInt , ĊĠĠĠ Ġprivate Ġval Ġstrategy : ĠStrategy , ĊĠĠĠ Ġlast Rem Edge : ĠPair < Int , ĠInt >? Ġ= Ġnull Ċ ) Ġ{ ĊĠĠĠ Ġvar Ġscore Ġby ĠDeleg ates . notNull < Int >() ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġupdate Score ( last Rem Edge ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠÐ ¤ ÑĥÐ½Ðº ÑĨÐ¸Ñı ĠÐ¿ÐµÑĢ ÐµÑģ Ñĩ Ñĳ ÑĤÐ° ĠÐ¾ ÑĨÐµÐ½ ÐºÐ¸ ĠÐ¿ÑĢÐ¸ ĠÐ¸Ð· Ð¼ÐµÐ½ ÐµÐ½Ð¸Ð¸ ĠÐ³ ÑĢÐ° ÑĦ Ð° . ĠÐĺ Ð· ĠÑģÐ¿Ð¸Ñģ ÐºÐ° ĠÐ½ ÐµÐ¿ ÑĢ Ð¾Ð¹ Ð´ ÐµÐ½ Ð½ÑĭÑħ ĠÑĢ Ñĳ Ð± ÐµÑĢ ĠÑĥ Ð± Ð¸ ÑĢÐ° ÐµÐ¼ ĠÑĤ Ðµ , ĊĠĠĠĠ Ġ* ĠÑĥ Ð´Ð°Ð» ÐµÐ½Ð¸Ðµ ĠÐºÐ¾ÑĤÐ¾ÑĢ ÑĭÑħ ĠÐ² ĠÐ¸ Ñģ ÑħÐ¾Ð´ Ð½Ð¾Ð¼ ĠÐ³ ÑĢÐ° ÑĦ Ðµ ĠÐ½Ð° ÑĢÑĥ ÑĪ Ð¸ÑĤ ĠÐµÐ³Ð¾ Ġk - Ñģ Ð² ÑıÐ· Ð½Ð¾ÑģÑĤÑĮ . ĊĠĠĠĠ Ġ* Ġ@ param Ġremoved Edge ĠÐ£ Ð´Ð°Ð» Ñĳ Ð½ Ð½Ð¾Ðµ ĠÑĢ ÐµÐ± ÑĢÐ¾ . ĊĠĠĠĠ Ġ* ĠÐķÑģÐ»Ð¸ ĠÐ½Ðµ Ġnull , ĠÑĤÐ¾ ĠÐ±ÑĥÐ´ ÑĥÑĤ ĠÑĢ Ð°ÑģÑģ Ð¼ Ð°ÑĤ ÑĢ Ð¸Ð² Ð°ÑĤÑĮÑģÑı ĠÑĤÐ¾Ð»ÑĮÐºÐ¾ ĠÑĢ Ñĳ Ð± ÑĢÐ° , ĠÐ¸Ð½ ÑĨÐ¸ Ð´ ÐµÐ½ÑĤ Ð½ÑĭÐµ ĠÐµÐ³Ð¾ ĠÐºÐ¾Ð½ ÑĨ Ð°Ð¼ . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġupdate Score ( removed Edge : ĠPair < Int , ĠInt >? Ġ= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( removed Edge Ġ!= Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem Un suit able Edges ( removed Edge ) ĊĠĠĠĠĠĠĠ Ġelse Ġgraph . get Edges (). forEach Ġ{ Ġrem Un suit able Edges ( it ) Ġ} ĊĠĠĠĠĠĠĠ Ġscore Ġ= Ġstrategy . evaluate ( this ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġrem Un suit able Edges ( removed Edge : ĠPair < Int , ĠInt >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġ( u , Ġv ) Ġ= Ġremoved Edge ĊĠĠĠĠĠĠĠ Ġgraph . com ( u ). map Ġ{ Ġit Ġto Ġu Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. plus ( graph . com ( v ). map Ġ{ Ġit Ġto Ġv Ġ}) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. forEach Ġ{ Ġ( s , Ġt ) Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( graph . deg ( s ) Ġ<= Ġk Ġ|| Ġgraph . deg ( t ) Ġ<= Ġk ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġraw Edges . remove ( s Ġto Ġt ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġraw Edges . remove ( t Ġto Ġs ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoperator Ġfun Ġcomponent 1 () Ġ= Ġgraph ĊĊĠĠĠ Ġoperator Ġfun Ġcomponent 2 () Ġ= Ġraw Edges Ċ } Ċ Ċ /** Ċ Ġ* ĠÐĺ Ð½ ÑĤÐµÑĢ ÑĦ ÐµÐ¹ Ñģ ĠÐ´Ð»Ñı ĠÑĥ Ð¿ÑĢÐ°Ð² Ð»ÐµÐ½Ð¸Ñı ĠÑģÑĤ ÑĢÑĥÐº ÑĤ ÑĥÑĢ Ð¾Ð¹ ĠÐ´ ÐµÑĢ ÐµÐ² Ð° ĠÐ¿Ð¾ Ð¸Ñģ ÐºÐ° ĠÐ² ĠÐ¼ÐµÑĤÐ¾Ð´ Ðµ ĠÐ² ÐµÑĤ Ð² ÐµÐ¹ ĠÐ¸ ĠÐ³ ÑĢ Ð°Ð½Ð¸ÑĨ . Ċ Ġ* Ġ` evaluate ` ĠÐ½ ÑĥÐ¶ ÐµÐ½ ĠÐ´Ð»Ñı ĠÐ²Ñĭ Ñĩ Ð¸Ñģ Ð»ÐµÐ½Ð¸Ñı ĠÐ¾ ÑĨÐµÐ½ Ð¾Ðº ĠÑĥ Ð· Ð» Ð¾Ð² ĠÐ´ ÐµÑĢ ÐµÐ² Ð° Ġ( Ð¿ Ð¾Ð´ Ð³ ÑĢÐ° ÑĦ Ð¾Ð² ), Ċ Ġ* ĠÑĩ ÐµÐ¼ ĠÐ½ Ð¸ Ð¶Ðµ ĠÐ¾ ÑĨÐµÐ½ ÐºÐ° , ĠÑĤ ÐµÐ¼ ĠÑĢ Ð°Ð½ ÑĮ ÑĪÐµ ĠÐ¾ Ð½ ĠÐ¾Ð± ÑĢÐ°Ð±Ð¾ÑĤ Ð°ÐµÑĤÑģÑı Ġ( ÑĤ . Ðº . ĠÐ·Ð°Ð´ Ð°Ñĩ Ð° ĠÐ¼ Ð¸Ð½ Ð¸Ð¼ Ð¸Ð· Ð°ÑĨÐ¸Ð¸ ), ĠÐ° Ċ Ġ* Ġ` sort Edges ` Ġ- ĠÐ´Ð»Ñı ĠÐ·Ð°Ð´ Ð°Ð½Ð¸Ñı ĠÐ¿ Ð¾ÑĢ Ñı Ð´ ÐºÐ° ĠÑģÐ¾ Ñħ ÑĢÐ°Ð½ ÐµÐ½Ð¸Ñı ĠÑĢ Ñĳ Ð± ÐµÑĢ ĠÐ² ĠÐ³ ÑĢÐ° ÑĦ Ðµ Ġ( ÑĤ . Ðµ . ĠÑĥ Ð´Ð° Ð»Ñı ÑİÑĤÑģÑı ĠÑģ ĠÐºÐ¾Ð½ ÑĨ Ð° ) Ċ Ġ*/ Ċ interface ĠStrategy Ġ{ ĊĠĠĠ Ġfun Ġrecord ( graph : ĠGraph ): ĠInt ĊĠĠĠ Ġfun Ġevaluate ( sub : ĠSub graph ) Ġ= ĠInt . MIN _ VALUE ĊĠĠĠ Ġfun Ġsort Edges ( edges : ĠList < Pair < Int , ĠInt >>, Ġgraph : ĠGraph ) Ġ= Ġedges . to Mutable List () Ċ } Ċ Ċ private Ġclass ĠUn weighted Strategy Ġ: ĠStrategy Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġrecord ( graph : ĠGraph ) Ġ= Ġgraph . num Ed g ĊĊĠĠĠ Ġoverride Ġfun Ġevaluate ( sub : ĠSub graph ) Ġ= Ġmax ( ĊĠĠĠĠĠĠĠ Ġif Ġ( sub . k Ġ== Ġ 1 ) Ġsub . graph . num Ver Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġelse Ġceil ( sub . k Ġ* Ġsub . graph . num Ver Ġ/ Ġ 2 . 0 ). toInt (), ĊĠĠĠĠĠĠĠ Ġsub . graph . num Ed g Ġ- Ġsub . raw Edges . size ĊĠĠĠ Ġ) ĊĊĠĠĠ Ġoverride Ġfun Ġsort Edges ( edges : ĠList < Pair < Int , ĠInt >>, Ġgraph : ĠGraph ) Ġ= ĊĠĠĠĠĠĠĠ Ġedges . sorted With ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠComparator ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. comp aring < Pair < Int , ĠInt >, ĠInt > Ġ{ Ġ( u , Ġv ) Ġ-> Ġmin ( graph . deg ( u ), Ġgraph . deg ( v )) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. then Comp aring Ġ{ Ġ( u , Ġv ) Ġ-> Ġgraph . deg ( u ) Ġ+ Ġgraph . deg ( v ) Ġ}). to Mutable List () Ċ } Ċ Ċ private Ġclass ĠWeight ed Strategy Ġ: ĠStrategy Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġrecord ( graph : ĠGraph ) Ġ= Ġgraph . sum Weights ĊĊĠĠĠ Ġ/* override Ġfun Ġevaluate ( sub : ĠSub graph ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġsub . graph . sum Weights ĊĠĠĠ Ġ}*/ ĊĊĠĠĠ Ġoverride Ġfun Ġsort Edges ( edges : ĠList < Pair < Int , ĠInt >>, Ġgraph : ĠGraph ) Ġ= ĊĠĠĠĠĠĠĠ Ġedges . sorted With ( Comparator ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. comp aring < Pair < Int , ĠInt >, ĠInt > Ġ{ Ġgraph . get Weight Ed g ( it ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. then Comp aring Ġ{ Ġ( u , Ġv ) Ġ-> Ġmin ( graph . deg ( u ), Ġgraph . deg ( v )) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. then Comp aring Ġ{ Ġ( u , Ġv ) Ġ-> Ġgraph . deg ( u ) Ġ+ Ġgraph . deg ( v ) Ġ}). to Mutable List () Ċ } Ċ Ċ private Ġclass ĠG G Strategy Ġ: ĠStrategy Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġrecord ( graph : ĠGraph ) Ġ= Ġgraph . num Ed g Ċ } Ċ Ċ /** Ċ Ġ* ĠÐĿ Ð°Ñħ Ð¾Ð¶ Ð´ ÐµÐ½Ð¸Ðµ Ġk - Ñģ Ð² ÑıÐ· Ð½Ð¾Ð³Ð¾ ĠÐ¾ ÑģÑĤ Ð¾Ð² Ð½Ð¾Ð³Ð¾ ĠÐ¿Ð¾Ð´ Ð³ ÑĢÐ° ÑĦ Ð° ĠÑģ ĠÐ½Ð° Ð¸Ð¼ ÐµÐ½ÑĮ ÑĪ Ð¸Ð¼ ĠÑĩ Ð¸Ñģ Ð» Ð¾Ð¼ ĠÑĢ ÐµÐ± ÐµÑĢ . Ċ Ġ* Ċ Ġ* Ġ@ param Ġg ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠÐĺ Ñģ ÑħÐ¾Ð´ Ð½ÑĭÐ¹ ĠÐ³ ÑĢÐ° ÑĦ . Ċ Ġ* Ġ@ param Ġk ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠÐ¡ Ð² ÑıÐ· Ð½Ð¾ÑģÑĤÑĮ ĠÐ¸ ÑģÐº Ð¾Ð¼ Ð¾Ð³Ð¾ ĠÐ¿Ð¾Ð´ Ð³ ÑĢÐ° ÑĦ Ð° . Ċ Ġ* Ġ@ param Ġlocal Connectivity ĠÐ ¤ ÑĥÐ½Ðº ÑĨÐ¸Ñı ĠÐ¾Ð¿ ÑĢÐµÐ´ÐµÐ» ÐµÐ½Ð¸Ñı ĠÑģÐ² ÑıÐ· Ð½Ð¾ÑģÑĤÐ¸ Ġ( Ð¿ Ð¾ ĠÑĥ Ð¼ Ð¾Ð» Ñĩ Ð°Ð½Ð¸ Ñİ Ġ- ĠÑĢ Ñĳ Ð± ÐµÑĢ Ð½Ð°Ñı ĠÑģÐ² ÑıÐ· Ð½Ð¾ÑģÑĤÑĮ ). Ċ Ġ* Ġ@ return ĠÐŁ Ð¾Ð´ Ð³ ÑĢÐ° ÑĦ ĠÐ·Ð°Ð´ Ð°Ð½ Ð½Ð¾Ð¹ ĠÑģÐ² ÑıÐ· Ð½Ð¾ÑģÑĤÐ¸ ĠÑģ ĠÐ¼ Ð¸Ð½ Ð¸Ð¼ Ð°Ð»ÑĮ Ð½ÑĭÐ¼ ĠÑĩ Ð¸Ñģ Ð» Ð¾Ð¼ ĠÑĢ Ñĳ Ð± ÐµÑĢ . Ċ Ġ*/ Ċ fun Ġfind Sp anning K Connected Sub graph ( ĊĠĠĠ Ġg : ĠGraph , ĊĠĠĠ Ġk : ĠInt , ĊĠĠĠ Ġlocal Connectivity : Ġ(( Graph , ĠInt , ĠInt ) Ġ-> ĠInt ) Ġ= Ġ:: local Edge Connectivity , ĊĠĠĠ Ġstrategy : ĠStrategy Ġ= ĠUn weighted Strategy () Ċ ): ĠResult Ġ{ ĊĊĠĠĠ Ġrequire ( k Ġ> Ġ 0 ) ĊĠĠĠ Ġrequire ( connectivity ( g , Ġlocal Connectivity ) Ġ>= Ġk ) Ġ{ Ġ" The Ġgraph Ġmust Ġhave Ġconnectivity Ġ>= Ġ$ k " Ġ} ĊĠĠĠ Ġvar Ġrec Ġ= Ġstrategy . record ( g ) ĊĠĠĠ Ġvar Ġmin G Ġ= Ġg ĊĠĠĠ Ġvar Ġid Ġ= Ġ 0 L ĊĠĠĠ Ġval Ġtimestamps Ġ= ĠTimestamp s () ĊĊĠĠĠ Ġval Ġleaves Ġ= ĠTree Set ( Comparator ĊĠĠĠĠĠĠĠ Ġ. comp aring ( Sub graph :: score ) ĊĠĠĠĠĠĠĠ Ġ// . reversed () Ġ// ÐµÑģ Ð»Ð¸ ĠÑĢÐ°Ñģ Ðº Ð¾Ð¼ Ð¼ ÐµÐ½ÑĤ Ð¸ÑĢÐ¾Ð² Ð°ÑĤÑĮ , ĠÑĤÐ¾ ĠÐ±ÑĥÐ´ ÑĥÑĤ ĠÐ² ĠÐ½Ð° Ñĩ Ð°Ð» Ðµ ĠÐ³ ÑĢÐ° ÑĦ Ñĭ ĠÑģ ĠÐ¼ Ð°Ðº Ñģ Ð¸Ð¼ Ð°Ð»ÑĮ Ð½Ð¾Ð¹ ĠÐ¾ ÑĨÐµÐ½ Ðº Ð¾Ð¹ ĊĠĠĠĠĠĠĠ Ġ. then Comp aring Ġ{ Ġsub Ġ-> Ġsub . raw Edges . size Ġ} ĊĠĠĠĠĠĠĠ Ġ. then Comp aring Ġ{ Ġsub Ġ-> Ġsub . graph . name Ġ}) ĊĊĠĠĠ Ġleaves . add ( Sub graph ( g , Ġstrategy . sort Edges ( g . get Edges (), Ġg ), Ġk , Ġstrategy ) ĊĠĠĠĠĠĠĠ Ġ. apply Ġ{ Ġlogger . debug Ġ{ Ġ" Ðŀ ÑĨÐµÐ½ ÐºÐ° ĠÐ¸ Ñģ ÑħÐ¾Ð´ Ð½Ð¾Ð³Ð¾ ĠÐ³ ÑĢÐ° ÑĦ Ð° Ġ$ score " Ġ} Ġ}) ĊĊĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( leaves . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcur Elem Ġ= Ġleaves . poll First () !! ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Elem . score Ġ>= Ġrec ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( cur G , Ġcur Edges ) Ġ= Ġcur Elem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Edges . isEmpty ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġcur Edges . remove Last () /*. remove First () Ġ- ĠÑĩÑĤÐ¾Ð±Ñĭ ĠÐ½Ð° Ð¾Ð± Ð¾ÑĢ Ð¾ÑĤ */ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( local Connectivity ( cur G , Ġedge . first , Ġedge . second ) Ġ> Ġk ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew G Ġ= ĠAd jacency Matrix Graph ( cur G ). apply Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ed g ( edge ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġname Ġ= Ġid ++. toString () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Ð£ Ð´Ð° Ð»Ð¸ Ð»Ð¸ ĠÑĢ ÐµÐ± ÑĢÐ¾ Ġ$ edge ĠÑĥ ĠÐ³ ÑĢÐ° ÑĦ Ð° Ġ${ new G . name }. ĠÐĿ Ðµ ÑĦ Ð¸Ðº Ñģ Ð¸ÑĢÐ¾Ð² Ð°Ð½ Ð½ÑĭÐµ ĠÑĢ Ñĳ Ð± ÑĢÐ° : Ġ${ cur Elem . raw Edges }" Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnm Ġ= ĠSub graph ( new G , Ġstrategy . sort Edges ( cur Edges , Ġnew G ), Ġk , Ġstrategy , Ġlast Rem Edge Ġ= Ġedge ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . debug Ġ{ Ġ" Ðŀ ÑĨÐµÐ½ ÐºÐ° ĠÐ¿Ð¾Ð»ÑĥÑĩ Ð¸Ð² ÑĪ ÐµÐ³Ð¾ ÑģÑı ĠÐ³ ÑĢÐ° ÑĦ Ð° Ġ${ nm . score }" Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Rec Ġ= Ġstrategy . record ( new G ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Rec Ġ< Ġrec ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrec Ġ= Ġnew Rec ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlogger . info Ġ{ Ġ" Ð¢ ÐµÐ¿ ÐµÑĢ ÑĮ ĠÑĢ ÐµÐº Ð¾ÑĢ Ð´ Ġ$ rec " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin G Ġ= Ġnew G ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtimestamps . make () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleaves . remove If Ġ{ Ġit . score Ġ>= Ġrec Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nm . score Ġ< Ġrec Ġ&& Ġ! leaves . add ( nm )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠIllegalArgumentException (" Ð§ ÑĤÐ¾ ĠÑĤÐ¾ ĠÐ¿Ð¾ ÑĪ Ð»Ð¾ ĠÐ½Ðµ ĠÑĤÐ°Ðº Ġ 1 .") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Elem . update Score () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Elem . score Ġ< Ġrec Ġ&& Ġ! leaves . add ( cur Elem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. apply Ġ{ Ġgraph . name Ġ= Ġid ++. toString () Ġ}) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġthrow ĠIllegalArgumentException (" Ð§ ÑĤÐ¾ ĠÑĤÐ¾ ĠÐ¿Ð¾ ÑĪ Ð»Ð¾ ĠÐ½Ðµ ĠÑĤÐ°Ðº Ġ 2 .") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ġcatch Ġ( e : ĠOut Of Memory Error ) Ġ{ ĊĠĠĠĠĠĠĠ Ġlogger . error ( e ) Ġ{ Ġ" ÐĴ Ñģ ÐµÐ³Ð¾ ĠÐ³ ÑĢÐ° ÑĦ Ð¾Ð² : Ġ${ leaves . size }" Ġ} ĊĠĠĠĠĠĠĠ Ġthrow Ġe ĊĠĠĠ Ġ} ĊĠĠĠ Ġlogger . info Ġ{ Ġ" Ðł ÐµÐº Ð¾ÑĢ Ð´ : Ġ$ rec " Ġ} ĊĠĠĠ Ġlogger . debug Ġ{ Ġ" Ðĺ Ñģ ÑħÐ¾Ð´ Ð½ÑĭÐ¹ ĠÐ³ ÑĢÐ° ÑĦ : Ġ$ g " Ġ} ĊĠĠĠ Ġlogger . debug Ġ{ Ġ" ÐŁ Ð¾Ð» ÑĥÑĩ Ð¸Ð² ÑĪÐ¸ Ð¹ ÑģÑı ĠÐ³ ÑĢÐ° ÑĦ : Ġ$ min G " Ġ} ĊĠĠĠ Ġtimestamps . make () ĊĠĠĠ Ġreturn ĠResult ( min G , Ġrec , Ġtimestamps ) Ċ } Ċ Ċ data Ġclass ĠResult ( val Ġanswer : ĠGraph , Ġval Ġrec : ĠInt , Ġval Ġtimestamps : ĠTimestamp s ) Ċ Ċ class ĠTimestamp s Ġ{ ĊĠĠĠ Ġprivate Ġval Ġstart Ġ= ĠSystem . currentTimeMillis () ĊĠĠĠ Ġprivate Ġvar Ġtimes Ġ= Ġmutable ListOf < Long >() ĊĊĠĠĠ Ġfun Ġget () Ġ= Ġtimes . map Ġ{ Ġit Ġ- Ġstart Ġ} ĊĊĠĠĠ Ġfun Ġmake () Ġ= Ġtimes . add ( System . currentTimeMillis ()) Ċ } Ċ