package Ġchapter 1 . section 5 Ċ Ċ import Ġedu . pr inc et on . cs . al gs 4 . In Ċ import Ġextensions . format Double Ċ import Ġextensions . sp endTime Millis Ċ Ċ /** Ċ Ġ* Ġå°Ĩ æķ´æķ° å¯¹ åħ¨éĥ¨ æ·»åĬł åĪ° UF ç±» ä¸Ń ï¼Į è¿ĶåĽŀ æľĢç»Ī çļĦ èģĶ ç»ĵ æķ° åĴĮ æ¶Ī èĢĹ çļĦæĹ¶éĹ´ Ċ Ġ*/ Ċ fun Ġunion Find ( uf : ĠU F , Ġpair Array : ĠArray < Pair < Int , ĠInt >> ): ĠPair < Int , ĠLong > Ġ{ ĊĠĠĠ Ġval Ġtime Ġ= Ġspend Time Millis Ġ{ ĊĠĠĠĠĠĠĠ Ġpair Array . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġu f . union ( it . first , Ġit . second ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġu f . count () Ġto Ġtime Ċ } Ċ Ċ /** Ċ Ġ* Ġä»İ æĸĩä»¶ ä¸Ń è¯»åıĸ æľĢå¤§ åĢ¼ N åĴĮ æķ´æķ° å¯¹ Ċ Ġ* ĠåıĤæķ° åıª æİ¥åıĹ ä¸īä¸ª åĢ¼ ï¼Į 1 Ġ 2 Ġ 3 ï¼Į åĪĨåĪ« å¯¹åºĶ å°ı è§Ħ æ¨¡ ãĢģ ä¸Ń çŃī è§Ħ æ¨¡ ãĢģ è¶ħ å¤§ è§Ħ æ¨¡ Ċ Ġ*/ Ċ fun Ġget N And Pair Array FromFile ( scale : ĠInt ): ĠPair < Int , ĠArray < Pair < Int , ĠInt >>> Ġ{ ĊĠĠĠ Ġval Ġpath Ġ= Ġwhen Ġ( scale ) Ġ{ ĊĠĠĠĠĠĠĠĠ 2 Ġ-> Ġ"./ data / medium UF . txt " ĊĠĠĠĠĠĠĠĠ 3 Ġ-> Ġ"./ data / large UF . txt " ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ"./ data / tiny UF . txt " ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġinput Ġ= ĠIn ( path ) ĊĠĠĠ Ġ// N è¡¨ç¤º æķ´æķ° å¯¹ åĪĹè¡¨ ä¸ŃçļĦ æľĢå¤§ åĢ¼ ĊĠĠĠ Ġval ĠN Ġ= Ġinput . readInt () ĊĠĠĠ Ġval Ġarray Ġ= Ġinput . read All Ints () ĊĠĠĠ Ġval Ġpair Array Ġ= ĠArray ( array . size Ġ/ Ġ 2 ) Ġ{ Ġarray [ it Ġ* Ġ 2 ] Ġto Ġarray [ it Ġ* Ġ 2 Ġ+ Ġ 1 ] Ġ} ĊĠĠĠ Ġreturn ĠN Ġto Ġpair Array Ċ } Ċ Ċ inline Ġfun Ġunion Find Test ( create : Ġ( Int ) Ġ-> ĠU F ) Ġ{ ĊĠĠĠ Ġvar Ġsize Ġ= Ġ 1 0 0 0 ĊĠĠĠ Ġvar Ġpre Time Ġ= Ġ 0 L ĊĠĠĠ Ġval Ġpair Ġ= Ġget N And Pair Array FromFile ( 3 ) ĊĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġu f Ġ= Ġcreate ( pair . first ) ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġunion Find ( uf , Ġpair . second . copyOf Range ( 0 , Ġmin Of ( size , Ġpair . second . size ))) ĊĠĠĠĠĠĠĠ Ġval Ġratio Ġ= Ġif Ġ( pre Time Ġ== Ġ 0 L ) Ġ"/" Ġelse Ġformat Double ( result . second . toDouble () Ġ/ Ġpre Time , Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġprintln (" union Num =${ min Of ( size , Ġpair . second . size )} Ġremaining Amount =${ result . first } Ġspend Time =${ result . second } ms Ġratio =${ ratio }") ĊĠĠĠĠĠĠĠ Ġpre Time Ġ= Ġresult . second ĊĠĠĠĠĠĠĠ Ġif Ġ( size Ġ>= Ġpair . second . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsize Ġ*= Ġ 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }