disjoyint-settu daatta ghadana

computer shaasthrathil, union-fined daatta structure allengil merj-fined settu ennum vilikkunna oru disjoyint-settu daatta structure, disjoyint (overlapping allatha) settukalude shekharam sambharikkunna oru daatta structureanu. thulyamaayi, ithu oru settinte oru vibhajanam disjoyint subsettukalaayi sambharikkunnu. puthiya settukal cherkkunnathinum settukal layippikkunnathinum (avaye avayude union upayogichu maattisthaapikkunnathinum) oru settile oru prathinidhi amgathe kandethunnathinumulla pravartthanangal ithu nalkunnu. avasaanathe pravartthanam eathenkilum rund gadakangal ore settilaano atho vyathyastha settilaano ennu kaaryakshamamaayi kandethaan sahayikkunnu.
disjoyint-settu dattaa strectureukal nadappilakkaan niravadhi maargangalundengilum, praayogikamaayi avaa palappozhum disjoyint-settu phoorast ennu vilikkunna oru prathyeka nadappaakkalumaayi thirichariyappedunnu. ithu oru prathyeka tharam vanamaan, ithu unionukal nadathukayum sthiramaaya thirichadavu samayat kandethukayum cheiyunnu. nodukalulla oru disjoyant-settu vanathil kootticherkkal, union allengil pravartthanangal kandethal ennivayude oru shreni nadatthaan motham samayam aavasyamaanu, athil valare pathukke valarunna vipareeta ackerman function evideyaanu. oro pravartthanatthinteyum adisthaanathil eee prakadanam urappunalkunnilla. vyakthigatha union fined ooppareshanukalum sthiramaaya samayathekkaal kooduthal samayamedukkumenkilum oro ooppareshanum thudarchayaaya pravartthanangal vegathilaakkaan disjoyint settu phoorast svayam krameekarikkaan kaaranamaakunnu. asymptotic aayi opttimalum praayogikamaayi kaaryakshamavumaan disjoyint settu vanangal.
oru graafinte ettavum kuranja spanning trea kandethunnathinulla kruskalinte algorithathil disjoyant-settu dattaa strectureukal oru pradhana punk vahikkunnu. minimum spanning treakalude praadhaanyam ardhamaakkunnathu disjoyint-settu dattaa strectureukal vaividhyamaarnna algorithangalkku adivarayidunnu ennaanu. koodaathe, disjoyant-settu dattaa gadanakalkku pratheekathmaka kanakkukootalinum athupole compilerukalilum, prathyekichu rajisttar alokkeshan prasnangalkkum prayogangalundu.
charithram.
bernard eiii aanu aadyamaayi bhinnatha niranja vanangale vivarichathu. galler maikkal jeey. 1964-ll fisher. 1973-ll, avarude samaya sankeernnatha hopcroftum ulman formula 2-nte aavarthichulla logaritham formula 1-maayi parimithappedutthiyirunnu. 1975ll, algorithathinte samaya sankeernathayil formula _ 3 (invezhs ackerman function) upper boundu ennu aadyamaayi theliyichathu roobert taarjanaan. athu kaduppamullathaanennu addeham theliyichu. galler-fisher ghadana ulppedunna oru prathyeka klaas algorithangalude thaazhnna paridhiyaanith ennu 1979 ll addeham kaanichu. 1989-ll, fredman saxes formula 5 bittukalude formula 4 (amortised) vaakkukal oro pravartthanatthinum "eathenkilum" disjoyint-settu dattaa structure upayogichu axus cheyyanamennu kaanichu, athuvazhi eee modelle dattaa gadanayude optimaalitti theliyikkunnu.
1991ll galeel itaaliyanoyum disjoyant settukalkkaayulla dattaa gadanakalekkurichulla oru sarway prasidheekarichu.
1994ll richard jeey. aandezhsanum heather volum orikkalum thadayenda aavashyamillaatha union-findinte samanthara pathipp vivarichu.
2007-ll sylwane konchanum jeane-christoph filliyattarum disjoyint-settu phoorast daatta gadanayude oru ardha-sthirathayulla pathipp vikasippikkukayum proof asisttant qoq upayogichu athinte krithyatha aupachaarikamaakkukayum cheythu. "ardha-sthiratha" ennaal gadanayude muun pathippukal kaaryakshamamaayi nilanirthappedunnu, ennaal dattaa gadanayude muun pathippukal axus cheiyunnathu pinneedullava asaadhuvaayitheerunnu. avayude ettavum vegathayeriya nadappaakkal sthirathayillaatha algoritam pole thanne kaaryakshamamaya prakadanam kaivarikkunnu. avar sankeernnatha vishakalanam nadathunnilla.
niyantrithamaaya prashnangalude vibhaagathil mikacha prakadanamulla disjoyant-settu dattaa gadanakalude vakabhedangalum pariganichittundu. saadhyamaaya unionukal chila vazhikalil niyanthrikkukayaanenkil, yadhaarthathil oru leanier time algoritam saadhyamaanennu gabo tarjan kaanichu.
praathinidhyam.
oru disjoyint-settu vanathile oro nodilum oru pooyintarum chila sahaaya vivarangalum adangiyirikkunnu, onnukil oru valuppamo ranco (pakshe randum allah). oru vrukshathinte verallaatha oro node athinte perantilekku viral choondunna perent pooyintar treakal nirmmikkaan pooyintarukal upayogikkunnu. root nodukale mattullavaril ninnu verthirichariyaan, avayude paarant poyintarukalkku nooad allengil centinal moolyam polulla vrithaakrithiyilulla reference polulla asaadhuvaaya moolyangalundu. oro maravum vanathil sookshichirikkunna oru koottatthe prathinidheekarikkunnu, settile amgangal maratthile nodukalaanu. root nodukal settu prathinidhikal nalkunnu nodukal adangiyirikkunna marangalude verukal thulyamaanengil maathram rund nodukal ore settilaanu.
vanathile nodukal aaplikkeshanu soukaryapradamaaya eathu vidhathilum sambharikkaan kazhiyum, ennaal avaa oru shreniyil sookshikkuka ennathaanu oru saadhaarana saankethikavidya. eee saahacharyathil, maathaapithaakkale avarude shreni soochikayiloode soochippikkaam. oro shreni entrich paarant pooyintarinaayi bitt storeju aavasyamaanu. backie praveshanathinu thaarathamyappeduthaavunnatho kuravo sambharanam aavasyamaanu, athinaal vanam sambharikkaan aavashyamaaya bittukalude ennam. oru nadappaakkal nischitha valippamulla nodukal upayogikkukayaanenkil (athuvazhi sambharikkaan kazhiyunna vanathinte paramavadhi valuppam parimithappedutthunnu), aavashyamaaya sambharanam leanier inn aanu.
pravartthanangal.
disjoyant-settu dattaa strectureukal moonnu pravartthanangale pinthunaykkunnu oru puthiya ghadakam adangiya oru puthiya settu nirmmikkuka; thannirikkunna ghadakam adangiya settinte prathinidhi kandethuka; rund settukal layippikkuka.
puthiya settukal undaakkuka.
kokwos _ 1 ooppareshan puthiya ghadakam maathram adangiya oru puthiya settilekku oru puthiya ghadakam cherkkukayum puthiya settu dattaa ghadanayil cherkkukayum cheiyunnu. pakaram dattaa ghadana oru settinte paarteeshanaayi kaanukayaanengil, coach _ 1 ooppareshan puthiya ghadakam cherthu settu valuthaakkukayum puthiya ghadakam maathram adangiya oru puthiya upavibhaagathilekku puthiya ghadakam idunnathiloode nilavilulla partition vipuleekarikkukayum cheiyunnu.
oru disjoyint-settu forestil, nodinte paarant pooyintarum nodinte valuppamo ranco kokvi _ 1 aarambikkunnu. oru roottine svayam choondikkaanikkunna oru nooad prathinidheekarikkunnuvel, oru ghadakam cherkkunnath inipparayunna seudocode upayogichu vivarikkaam
 function mesettu ("x") aanu
 x" ithinakam vanathilillengil
 "x".rakshakarthaava = "x"
 "x".valippam = 1 "// nodukal valippam sambharichaal"
 "x".ranka = 0 "// nodukal rank sambharichaal"
 avasaanippikkukayaanenkil
 end function
eee pravarthanatthinu sthiramaaya samaya sankeernathayundu. prathyekichum, oru aarambhikkunnath
nodukalulla vighadippicha vanam aavasyamaanu 
samayam.
praayogikamaayi, pidichunirtthaan memory anuvadikkunna oru ooppareshan kokvi _ 1 nuu munbaayirikkanam. memory alokkeshan oru amortised konsttant-time ooppareshan aayirikkunnidatholam kaalam, ithu oru nalla dynamic shreni nadappakkalinu vendiyullathaanu, ithu kramarahithamaya vanathinte lakshanangalillaatha prakadanatthe mattilla.
settu prathinidhikale kandethuka.
oru root gadakathilethunnathuvare oru nirddishta kwari nodil ninnu paarant pooyintarukalude shringalaye kokwos _ 5 ooppareshan pinthudarunnu. eee root ghadakam eathu settilaanu ulppettirikkunnathum athu thanne aayirikkunnathum ennathine prathinidheekarikkunnu. kokwos _ 5 athu athunna root ghadakam nalkunnu.
oru kookk ooppareshan nadathunnathu vanam mechappeduthunnathinulla oru pradhana avasaram nalkunnu. oru kookk 5 ooppareshanile samayam maathru pooyintarukale pinthudarunnathil chelavazhikkunnu, athinaal oru paranna maram vegathayeriya kookk 5 ooppareshanukalilekku nayikkunnu. oru kookk _ 5 nadappilaakkumbol, oro paarant pooyintarum thudarchayaayi pinthudarunnathinekkaal vegathil roottil ethaan margamilla. ennirunnaalum, eee thirayalinide sandarshicha maathru pooyintarukal rutinode kooduthal adukkunnathinaayi update cheyyaan kazhiyum. oru verilekkulla vazhiyil sandarshikkunna oro moolakavum ore koottatthinte bhagamaayathinaal, ithu kattil sookshichirikkunna koottangale mattunnilla. ennaal ithu kwari nodinum rootinum edayilulla nodukalkku mathramalla, avarude pingaamikalkkum bhaaviyile kokwos 5 pravartthanangal vegathilaakkunnu. eee update cheiyunnathu disjoyint-settu forestinte amortised perfomence gyarandiyude oru pradhana bhagamaanu.
asymptoticalaayi opttimal samaya sankeernnatha kaivarikkunna niravadhi algorithangal kokwos _ 5-naayi undu. paathu compression ennariyappedunna algorithangalude oru kudumbam, kwari nodinum root pooyintinum edayilulla oro nodineyum rootilekku maattunnu. thaazhepparayunna lalithamaaya aavarthanam upayogichu paathu compression nadappilaakkaam
 function fined ("x") aanu
 x" aanenkil.appol rakshaakarthaav σ "x
 "x".rakshaakarthaava = kandethuka ("x".maathaapithaakkal)
 x" ennu thirike nalkuka.maathaapithaakkal
 mattenthenkilum
 x" thirike nalkuka"
 avasaanippikkukayaanenkil
 end function
eee nadappaakkal rund paasukal undaakkunnu, onnu maratthinu mukalilekkum onnu thaazhekkum. kwayari nodil ninnu roottilekkulla paatha sambharikkaan mathiyaya scratch memory aavasyamaanu (mukalil paranja seudocodil, kooll staakk upayogichu paatha parokshamaayi prathinidheekarikkunnu). rund paasukalum ore dishayil nadathunnathiloode ithu sthiramaaya memmariyaayi kuraykkaan kazhiyum. sthiramaaya memory nadappaakkal kwari nodil ninnu rootilekku randuthavana nadakkunnu, orikkal root kandethaanum orikkal pooyintarukal update cheyyanum
 function fined ("x") aanu
 "root": = "x"
 root".rakshaakarthaav ≤ "root" cheyyuka
 "root": = "root".maathaapithaakkal
 avasaanikkumbol
 athesamayam "x".rakshaakarthaav ≤ "root" cheyyuka
 "rakshaakarthaav": = "x".maathaapithaakkal
 "x".rakshaakarthaava = "root"
 "x": = "" rakshaakarthaav "
 avasaanikkumbol
 root" thirike nalkuka"
 end function
tarjan vaan leuven ore mosham-cases sankeernnatha nilanirthukayum ennaal praayogikamaayi kooduthal kaaryakshamamakkukayum cheiyunna vann-paas kokwos _ 5 algorithangalum vikasippichu. ivaye paatha vibhajanam, paatha pakuthi ennu vilikkunnu. iva randum kwari nodinum rootinum edayilulla paathayile nodukalude paarant pooyintarukal update cheiyunnu. paathu splitting aaa paathayile oro paarant pooyintarinum pakaram nodinte muthachanilekkulla oru pooyintar upayogikkunnu
 function fined ("x") aanu
 athesamayam "x".rakshaakarthaav ≤ "x" cheyyuka
 ("x", "x".rakshakarthaavu): = ("x".x", enna perant.maathaapithaakkal.maathaapithaakkal)
 avasaanikkumbol
 x" thirike nalkuka"
 end function
paathayude pakuthi samaanamaayi pravartthikkunnu, pakshe matellaa maathru pooyintarukalkkum pakaram vaykkunnu
 function fined ("x") aanu
 athesamayam "x".rakshaakarthaav ≤ "x" cheyyuka
 "x".rakshaakarthaava = "x".maathaapithaakkal.maathaapithaakkal
 "x": = "" x "." maathaapithaakkal
 avasaanikkumbol
 x" thirike nalkuka"
 end function
rund settukal samyojippikkuka.
ooppareshan cocks _ 14 adangiya settineyum avayude union ulkkollunna settineyum maattisthaapikkunnu. cockways _ 15 aadyam cockways _ 5 upayogikkunnu, koodaathe avaa adangiyirikkunna marangalude verukal nirnnayikkunnu. verukal onnuthanneyaanenkil, kooduthalonnum cheyyaanilla. allengil, rund marangalum layippikkanam. onnukil 's' nte roottinte paarant pooyintar 's' aayi sajjeekaricho allengil 's' nte roottinte paarant pooyintar 's' aayi sajjeekaricho aanu ithu cheiyunnathu.
eathu nooad rakshaakarthaavaayi maarunnu ennathu maratthile bhaavi pravartthanangalude sankeernathaykku anantharafalangal undaakkunnu. ashradhamaayi cheythaal marangalkk amita uyaram vannekkaam. udaaharanathinu, cocks 15 ellaayppozhum oru upavrikshamulla maratthe nirmmichuvennu karuthuka. soothravaakyam _ 6 upayogichu aarambikkappetta oru vanathil ninnu aarambhich qoq 18, qoq 18, nadappilaakkuka...18. falamaayundaakunna vanathil verulla orotta maravum 1 muthal maratthile oro nodiloodeyum kadannupokunna pathayum adangiyirikkunnu. eee vanathe sambandhichidatholam, kookk _ 21 oodaanulla samayamaan.
kaaryakshamamaya nadappakkalil, valippam anusarichu union allengil rank anusarichu union upayogichu marangalude uyaram niyanthrikkunnu. iva randinum athinte paarant poyintarinu purame vivarangal sambharikkunnathin oru nooad aavasyamaanu. eathu root puthiya rakshaakarthaavaanennu theerumaanikkaan eee vivarangal upayogikkunnu. marangal valare aazhathilaakaathirikkaan rund thanthrangalum urappaakkunnu.
valippam anusarichu union.
valippam anusarichu yooniyante kaaryatthil, oru nooad athinte valippam sambharikkunnu, athu athinte pingaamikalude ennam (nooad ulppede) maathramaan. verukalulla marangal layippikkappedumbol, kooduthal pingaamikalulla nooad rakshakarthavaayi maarunnu. rund nodukalkkum ore ennam pingaamikalundenkil, orennathinu rakshaakarthaavaakaan kazhiyum. rund saahacharyangalilum, puthiya paarant nodinte valippam athinte puthiya motham pingaamikalude ennathilekku krameekarichirikkunnu.
 function union ("x", "y")
 "// nodukalkku pakaram roottukal"
 "x": = kandethuka ("x")
 "y": = kandethuka ("y")
 x" = "y" aanenkil
 ritten "// x umm y umm ithinakam ore settilaanu"
 avasaanippikkukayaanenkil
 "// aavashyamenkil, athu urappakkaan variableukal maattuka"
 "// x nuu kuranjathu y-neppole niravadhi pingaamikalundaakum"."
 x" aanenkil.valippam <"y".appol valippam
 ("x", "y"): = ("y", "x")
 avasaanippikkukayaanenkil
 "// x neey puthiya root aakkuka"
 "vaii".rakshakarthaava = "x"
 "// x-nte valippam update cheyyuka"
 "x".valippam = "x".valippam + "y".valippam
 end function
valuppam sambharikkaan aavashyamaaya bittukalude ennam vyakthamaayi sambharikkaan aavashyamaaya bittukalude ennamaanu. ithu vanathinte aavashyamaaya sambharanathinu sthiramaaya oru ghadakam cherkkunnu.
rank anusarichu union.
rank anusarichu union cheiyunnathinu, oru nooad athinte uyarathinu mukalilulla oru paridhiyaya athinte nooad sambharikkunnu. oru nooad aarambhikkumbol, athinte rank poojyamaayi sajjeekarikkunnu. marangale verukalumaayi layippikkukayum aadyam avayude raankukal thaarathamyam cheyyukayum cheyyuka. raankukal vyathyasthamaanenkil, valia rank trea rakshaakarthaavaayi maarunnu, raankukal marunnilla. raankukal onnuthanneyaanenkil, randiloraalkk rakshaakarthaavaakaan kazhiyum, ennaal puthiya rakshaakarthaavinte rank onnu vardhippikkum. oru nodinte rank athinte uyaravumaayi vyakthamaayi bandhappettirikkumbol, raankukal sambharikkunnath uyarangal sambharikkunnathinekkaal kaaryakshamamaan. oru kokwos _ 5 ooppareshan samayat oru nodinte uyaram mariyekkaam, athinaal raankukal sambharikkunnath uyaram shariyaayi nilanirthaanulla adhika sramam ozhivaakkunnu. seudocodil, rank anusarichu union ithaanu
 function union ("x", "y")
 "// nodukalkku pakaram roottukal"
 "x": = kandethuka ("x")
 "y": = kandethuka ("y")
 x" = "y" aanenkil
 ritten "// x umm y umm ithinakam ore settilaanu"
 avasaanippikkukayaanenkil
 "// aavashyamenkil, athu urappakkaan veriyabilukalude peru maattuka"
 "// x nuu kuranjathu y-yude athra valia rankenkilum undu"."
 x" aanenkil.rank <"y".appol rank
 ("x", "y"): = ("y", "x")
 avasaanippikkukayaanenkil
 "// x neey puthiya root aakkuka"
 "vaii".rakshakarthaava = "x"
 "// aavashyamenkil, x-nte rank vardhippikkuka"
 x" aanenkil.rank = "y".appol rank
 "x".ranka = "x".rank + 1
 avasaanippikkukayaanenkil
 end function
oro nodinum rank formula _ 7 allengil athil kuravaanennu kaanikkam. thathfalamaayi oro rankum bittukalil sambharikkaanum ellah raankukalum bittukalil sambharikkaanum kazhiyum. ithu raankukale vanathinte valippathinte lakshanangalillaatha oru bhagamaakki maattunnu.
oru nooad oru vrukshathinte verallengil oru nodinte valipavum rankum prashnamallenn melpparanja nadappaakkalukalil ninnu vyakthamaan. oru nooad child aayikkazhinjaal, athinte valupavum rankum orikkalum veendum axus cheyyappedilla.
samaya sankeernnatha.
cocos 5 maathru pooyintarukal update cheyyaathathum, cocos 15 marangalude uyaram niyantrikkaan sramikkaathathumaaya oru bhinna-settu phoorast nadappakkalil uyaramulla marangal undakam. atharamoru saahacharyathil, kookk 5, kookk 15 pravarthanangalkku samayam aavasyamaanu.
oru nadappaakkal paathu compression maathram upayogikkukayaanenkil, thudarnnu kookk 15 pravartthanangalum kookk 5 pravartthanangalum vareyulla kookk 1 pravartthanangalude oru shreniyil formula 8 nte ettavum mosham pravartthana samayamundu.
rank anusarichu union upayogikkunnathu, ennaal kokvi _ 5 samayat rakshaakarthru pooyintarukal update cheyyaathe, eathu tharatthilulla pravarthanangalkkum formula _ 9 nte pravartthana samayam nalkunnu, avayil kokvi _ 1 pravarthanangalaanu.
paathu compression, splitting allengil pakuthi, valippam allengil rank anusarichu union, formula 10 lake eathu tharatthilulla pravarthanangalkkum pravartthana samayam kuraykkunnu, athil kokosiooonu ooppareshanukal vare, ithu oro ooppareshan formulayude amortised running time akkunnu. ithu lakshanangalillaatha opttimal aanu, athaayath oro disjoyint settu daatta ghadanayum oro ooppareshanum formula _ 4 amortised samayam upayogikkanam. ivide, function formula _ 13 invezhs ackerman functionaanu. vipareeta ackerman function asaadhaaranamaamvidham saavadhaanathil valarunnu, athinaal eee ghadakam bhauthika prapanchatthil yadhaarthathil ezhuthaan kazhiyunna eathoru gadakathinum allengil athil kuravaanu. ithu disjoyant-settu pravartthanangale praayogikamaayi sthiramaaya samayamakki maattunnu.
union-findinte samaya sankeernathayude thelivu o (m log * n).
oru bhinnasankaramaaya vanathinte prakadanathekkurichulla krithyamaaya vishakalanam alppam sankeernamaanu. ennirunnaalum, vasthukkal adangiya oru disjoyint-settu vanathile eathenkilum kokwos _ 5 allengil kokwos _ 15 pravarthanangalkkulla kadamedukkunna samayam aavarthichulla logarithathe soochippikkunnuvennu theliyikkunna valare lalithamaaya oru vishakalanam undu.
lemma 1: fined function roottilekkulla paatha pinthudarunnathinaal, athu abhimukeekarikkunna nodinte rank vardhichukondirikkanu.
lemma 2: raankulla oru subtreeyude root aaya oru nodinu kuranjathu formula _ 14 nodukalundaakum.
lemma 3: rankinginte nodukalude paramavadhi ennam formula _ 15 aanu.
soukaryathinaayi, njangal ivide "bucket" nirvachikkunnu oru bucket ennathu prathyeka raankukalulla shringangal adangiya oru koottamaanu.
nammal chila bakkattukal srishtikkukayum bakkattukalil avayude raankukalkkanusarichu varkattukal idukayum cheiyunnu. athaayath, rank 0 ulla shringangal siroth bakkattilekku pookunnu, rank 1 ulla shringangal aadya bakkattilekku pookunnu, rank 2,3 ulla shringangal randaamathe bakkattilekku pookunnu. - th bakkattil edavela formula _ 16 ll ninnulla raankukalulla shringangal undengil (b + 1) staand bakkattil edavela formula _ 17 ll ninnulla raankukalulla shringangal adangiyirikkum.
bakkattukalekkurichu namukk rund nireekshanangal nadatthaam.
nadatthiya "fined" pravartthanangalude pattika prathinidheekarikkam,
formula _ 24
soothravaakyam _ 25
soothravaakyam _ 26
appol kandethalukalude motham chelavu formula _ 27 aanu.
oro fined ooppareshanum oru verilekku nayikkunna krithyamaayi oru traversal undakkunnathinaal, namukk undu.
koodaathe, mukalil paranjirikkunna bakkattukalude ennathil ninnu namukk undu.
kaaranam, nammal oru attathu sanjarikkukayaanennu karuthuka, evide ninnu, bakkattil rank undu, athu veralla (eee sanjarikkunna samayat, allengil traversal kanakkakkappedum). vyathyastha fined ooppareshanukalil punk vahikkunna sequence formula _ 28 sariyaakkukayum pariganikkukayum cheyyuka. paathu compression kaaranam, oru roottilekkulla edju kanakkaakkaathathinaal, eee shreniyil vyathyastha nodukal maathrame adangiyittulloo, lemma 1 kaaranam eee shreniyile nodukalude raankukal karsanamaayi vardhichukondirikkanu namukkariyam. rund nodukalum bakkattilaayirikkunnathil namukk nigamanam cheyyaan kazhiyum, shreniyude neelam (ore bakkattile mattoru roottil nooad ethra thavana gadippichirikkunnu) bakkattukalile raankukalude ennamaanu, athaayath, paramavadhi formula _ 29
athinaal, formula _ 30
1, 2 nireekshanangalil ninnu namukk aaa soothravaakyam _ 31 ennu nigamanam cheyyaam.
athinaal, soothravaakyam _ 32
mattu gadanakal.
oro shasthrakriyaykkum ettavum mosham samayam.
rank allengil thookkam anusarichu union ulla marangalile cocks 5 pravartthanatthinte ettavum mosham samayam formula 33 aanu (i.iii.ithu formula _ 5 aanu, eee boundu irukiyathaanu). 
1985ll enn. paathu compression upayogikkaatha, ennaal formula 35 samayat marangale compress cheiyunna pravartthanangalude nadappaakkal blum nalki. addehathinte nadappaakkal oro pravartthanatthinum formula 36 samayathilaan pravartthikkunnathu, athinaal gallerinteyum fisherinteyum gadanayumaayi thaarathamyappeduthumbol ithinu oro pravartthanatthinum mikacha mosham samayamundu, pakshe kuranja vaipa samayamundu. 1999ll, alstrup thudangiyavar. ettavum moshamaaya avasthayulla oru ghadana nalki
samaya soothravaakyam _ 36 invezhs-ackerman amortised samayathodoppam.
neekkam cheyyuka.
samyuktha vanangal enna nilayil pathivayi nadappaakkunnathu moolakangalude illathakkalinodu anukoolamaayi prathikarikkunnilla.
moolakangalude ennam kurayunnathinte falamaayi cocks _ 5-nte samayam mechappedilla enna ardhathil. ennirunnaalum, sthiramaaya samaya illaathaakkal anuvadikkunna aadhunika nadappaakkalukal nilavilundu, koodaathe kokvu _ 5-nte samayaparidhi gadakangalude "nilavile" ennathe aasrayichirikkunnu.
aaplikkeshanukal.
disjoyant-settu dattaa strectureukal oru settinte partitioning model cheiyunnu, udaaharanathinu, oru dishaabodhamillaatha graafinte connectucheytha gadakangalude track sookshikkaan. rund shringangal ore gadakathil pedunnundo atho avaykkidayil oru attam cherkkunnath oru chakratthinu kaaranamaakumo ennu nirnnayikkaan eee maathruka upayogikkaam. ekeekaranathinte uyarnna prakadanamulla nadappaakkalukalil union-fined algoritam upayogikkunnu.
eee dattaa ghadana boost graph library athinte incremental connected gadakangalude pravartthanam nadappilakkaan upayogikkunnu. oru graafinte ettavum kuranja spanning trea kandethunnathinayi kruskalinte algoritam nadappilaakkunnathile oru pradhana ghadakam koodiyaanithu.
hoshan-coppelman algoritam algorithathil oru union-fined upayogikkunnu.

