CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Disjoint-set data structure - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"ad5d1f5b-f1e7-4b76-8f33-49c182c2e88a","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Disjoint-set_data_structure","wgTitle":"Disjoint-set data structure","wgCurRevisionId":1267325423,"wgRevisionId":1267325423,"wgArticleId":1037551,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles with example pseudocode","Search algorithms","Amortized data structures"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Disjoint-set_data_structure","wgRelevantArticleId":1037551,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[], "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1259393","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth", "ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.17"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Disjoint-set data structure - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Disjoint-set_data_structure"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Disjoint-set_data_structure&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Disjoint-set_data_structure rootpage-Disjoint-set_data_structure skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Disjoint-set+data+structure" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Disjoint-set+data+structure" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Disjoint-set+data+structure" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Disjoint-set+data+structure" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-History" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>History</span> </div> </a> <ul id="toc-History-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Representation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Representation"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Representation</span> </div> </a> <ul id="toc-Representation-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Operations</span> </div> </a> <button aria-controls="toc-Operations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Operations subsection</span> </button> <ul id="toc-Operations-sublist" class="vector-toc-list"> <li id="toc-Making_new_sets" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Making_new_sets"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Making new sets</span> </div> </a> <ul id="toc-Making_new_sets-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Finding_set_representatives" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Finding_set_representatives"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Finding set representatives</span> </div> </a> <ul id="toc-Finding_set_representatives-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Merging_two_sets" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Merging_two_sets"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Merging two sets</span> </div> </a> <ul id="toc-Merging_two_sets-sublist" class="vector-toc-list"> <li id="toc-Union_by_size" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Union_by_size"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.1</span> <span>Union by size</span> </div> </a> <ul id="toc-Union_by_size-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Union_by_rank" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Union_by_rank"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.2</span> <span>Union by rank</span> </div> </a> <ul id="toc-Union_by_rank-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Time_complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Time_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Time complexity</span> </div> </a> <button aria-controls="toc-Time_complexity-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Time complexity subsection</span> </button> <ul id="toc-Time_complexity-sublist" class="vector-toc-list"> <li id="toc-Proof_of_O(m_log*_n)_time_complexity_of_Union-Find" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Proof_of_O(m_log*_n)_time_complexity_of_Union-Find"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Proof of O(m log* n) time complexity of Union-Find</span> </div> </a> <ul id="toc-Proof_of_O(m_log*_n)_time_complexity_of_Union-Find-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Other_structures" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Other_structures"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Other structures</span> </div> </a> <button aria-controls="toc-Other_structures-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Other structures subsection</span> </button> <ul id="toc-Other_structures-sublist" class="vector-toc-list"> <li id="toc-Better_worst-case_time_per_operation" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Better_worst-case_time_per_operation"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Better worst-case time per operation</span> </div> </a> <ul id="toc-Better_worst-case_time_per_operation-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Deletion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Deletion"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Deletion</span> </div> </a> <ul id="toc-Deletion-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Disjoint-set data structure</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 21 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-21" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">21 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%87%D9%8A%D9%83%D9%84%D8%A9_%D8%A8%D9%8A%D8%A7%D9%86%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D8%AC%D9%85%D9%88%D8%B9%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D9%86%D9%81%D8%B5%D9%84%D8%A9" title="هيكلة بيانات المجموعات المنفصلة – Arabic" lang="ar" hreflang="ar" data-title="هيكلة بيانات المجموعات المنفصلة" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%A1%E0%A6%BF%E0%A6%B8%E0%A6%9C%E0%A6%AF%E0%A6%BC%E0%A7%87%E0%A6%A8%E0%A7%8D%E0%A6%9F_%E0%A6%B8%E0%A7%87%E0%A6%9F_%E0%A6%A1%E0%A6%BE%E0%A6%9F%E0%A6%BE_%E0%A6%B8%E0%A7%8D%E0%A6%9F%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%95%E0%A6%9A%E0%A6%BE%E0%A6%B0" title="ডিসজয়েন্ট সেট ডাটা স্ট্রাকচার – Bangla" lang="bn" hreflang="bn" data-title="ডিসজয়েন্ট সেট ডাটা স্ট্রাকচার" data-language-autonym="বাংলা" data-language-local-name="Bangla" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%BE%D1%82_%D0%B4%D0%B0%D0%BD%D0%BD%D0%B8_%D0%B7%D0%B0_%D0%BD%D0%B5%D0%BF%D1%80%D0%B5%D1%81%D0%B8%D1%87%D0%B0%D1%89%D0%B8_%D1%81%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0" title="Структура от данни за непресичащи се множества – Bulgarian" lang="bg" hreflang="bg" data-title="Структура от данни за непресичащи се множества" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Union-Find-Struktur" title="Union-Find-Struktur – German" lang="de" hreflang="de" data-title="Union-Find-Struktur" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%94%CE%BF%CE%BC%CE%AE_%CE%BE%CE%AD%CE%BD%CF%89%CE%BD_%CF%83%CF%85%CE%BD%CF%8C%CE%BB%CF%89%CE%BD_(%CF%80%CE%BB%CE%B7%CF%81%CE%BF%CF%86%CE%BF%CF%81%CE%B9%CE%BA%CE%AE)" title="Δομή ξένων συνόλων (πληροφορική) – Greek" lang="el" hreflang="el" data-title="Δομή ξένων συνόλων (πληροφορική)" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Estructura_de_datos_para_conjuntos_disjuntos" title="Estructura de datos para conjuntos disjuntos – Spanish" lang="es" hreflang="es" data-title="Estructura de datos para conjuntos disjuntos" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%AC%D9%85%D9%88%D8%B9%D9%87%E2%80%8C%D9%87%D8%A7%DB%8C_%D9%85%D8%AC%D8%B2%D8%A7_(%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86_%D8%AF%D8%A7%D8%AF%D9%87)" title="مجموعه‌های مجزا (ساختمان داده) – Persian" lang="fa" hreflang="fa" data-title="مجموعه‌های مجزا (ساختمان داده)" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Union-find" title="Union-find – French" lang="fr" hreflang="fr" data-title="Union-find" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0" title="서로소 집합 자료 구조 – Korean" lang="ko" hreflang="ko" data-title="서로소 집합 자료 구조" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Mfset" title="Mfset – Italian" lang="it" hreflang="it" data-title="Mfset" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%90%D7%99%D7%97%D7%95%D7%93_%D7%A7%D7%91%D7%95%D7%A6%D7%95%D7%AA_%D7%96%D7%A8%D7%95%D7%AA" title="איחוד קבוצות זרות – Hebrew" lang="he" hreflang="he" data-title="איחוד קבוצות זרות" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0" title="素集合データ構造 – Japanese" lang="ja" hreflang="ja" data-title="素集合データ構造" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Struktura_zbior%C3%B3w_roz%C5%82%C4%85cznych" title="Struktura zbiorów rozłącznych – Polish" lang="pl" hreflang="pl" data-title="Struktura zbiorów rozłącznych" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Uni%C3%A3o-busca" title="União-busca – Portuguese" lang="pt" hreflang="pt" data-title="União-busca" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2" title="Система непересекающихся множеств – Russian" lang="ru" hreflang="ru" data-title="Система непересекающихся множеств" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D1%98%D1%83%D0%BD%D0%BA%D1%82%D0%BD%D0%B8-%D1%81%D0%B5%D1%82_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%BF%D0%BE%D0%B4%D0%B0%D1%82%D0%B0%D0%BA%D0%B0)" title="Дисјунктни-сет (структура података) – Serbian" lang="sr" hreflang="sr" data-title="Дисјунктни-сет (структура података)" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B9%82%E0%B8%84%E0%B8%A3%E0%B8%87%E0%B8%AA%E0%B8%A3%E0%B9%89%E0%B8%B2%E0%B8%87%E0%B8%82%E0%B9%89%E0%B8%AD%E0%B8%A1%E0%B8%B9%E0%B8%A5%E0%B9%80%E0%B8%8B%E0%B8%95%E0%B9%84%E0%B8%A1%E0%B9%88%E0%B8%A1%E0%B8%B5%E0%B8%AA%E0%B9%88%E0%B8%A7%E0%B8%99%E0%B8%A3%E0%B9%88%E0%B8%A7%E0%B8%A1" title="โครงสร้างข้อมูลเซตไม่มีส่วนร่วม – Thai" lang="th" hreflang="th" data-title="โครงสร้างข้อมูลเซตไม่มีส่วนร่วม" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%82%D0%B8%D0%BD%D0%BD%D0%B8%D1%85_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D0%BD" title="Система неперетинних множин – Ukrainian" lang="uk" hreflang="uk" data-title="Система неперетинних множин" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/C%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u_cho_c%C3%A1c_t%E1%BA%ADp_h%E1%BB%A3p_kh%C3%B4ng_giao_nhau" title="Cấu trúc dữ liệu cho các tập hợp không giao nhau – Vietnamese" lang="vi" hreflang="vi" data-title="Cấu trúc dữ liệu cho các tập hợp không giao nhau" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E4%BD%B5%E6%9F%A5%E9%9B%86" title="併查集 – Cantonese" lang="yue" hreflang="yue" data-title="併查集" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86" title="并查集 – Chinese" lang="zh" hreflang="zh" data-title="并查集" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1259393#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Disjoint-set_data_structure" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Disjoint-set_data_structure" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Disjoint-set_data_structure"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Disjoint-set_data_structure"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Disjoint-set_data_structure" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Disjoint-set_data_structure" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&oldid=1267325423" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Disjoint-set_data_structure&id=1267325423&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDisjoint-set_data_structure"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDisjoint-set_data_structure"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Disjoint-set_data_structure&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Disjoint-set_data_structure&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1259393" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Data structure for storing non-overlapping sets</div> <style data-mw-deduplicate="TemplateStyles:r1257001546">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme) div:not(.notheme){background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table tr{display:table-row!important}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Disjoint-set/Union-find Forest</th></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data">multiway tree</td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1964</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="/wiki/Bernard_A._Galler" class="mw-redirect" title="Bernard A. Galler">Bernard A. Galler</a> and <a href="/wiki/Michael_J._Fischer" title="Michael J. Fischer">Michael J. Fischer</a></td></tr><tr><td colspan="2" class="infobox-full-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1257001546"><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="/wiki/Time_complexity" title="Time complexity">Time complexity</a> in <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Operation</th><td class="infobox-data infobox-data-a"> <b>Average</b></td><td class="infobox-data infobox-data-b"> <b>Worst case</b></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Search</th><td class="infobox-data infobox-data-a"> <span class="texhtml"><i>O</i>(α(<i>n</i>))</span><sup id="cite_ref-tarjan1975_1-0" class="reference"><a href="#cite_note-tarjan1975-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> (amortized)</td><td class="infobox-data infobox-data-b"> <span class="texhtml"><i>O</i>(α(<i>n</i>))</span><sup id="cite_ref-tarjan1975_1-1" class="reference"><a href="#cite_note-tarjan1975-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> (amortized)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> <span class="texhtml"><i>O</i>(1)</span><sup id="cite_ref-tarjan1975_1-2" class="reference"><a href="#cite_note-tarjan1975-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td><td class="infobox-data infobox-data-b"> <span class="texhtml"><i>O</i>(1)</span><sup id="cite_ref-tarjan1975_1-3" class="reference"><a href="#cite_note-tarjan1975-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td></tr><tr><th colspan="4" class="infobox-header"><a href="/wiki/Space_complexity" title="Space complexity">Space complexity</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Space</th><td class="infobox-data infobox-data-a"> <span class="texhtml"><i>O</i>(<i>n</i>)</span><sup id="cite_ref-tarjan1975_1-4" class="reference"><a href="#cite_note-tarjan1975-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td><td class="infobox-data infobox-data-b"> <span class="texhtml"><i>O</i>(<i>n</i>)</span><sup id="cite_ref-tarjan1975_1-5" class="reference"><a href="#cite_note-tarjan1975-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td></tr></tbody></table></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>disjoint-set data structure</b>, also called a <b>union–find data structure</b> or <b>merge–find set</b>, is a <a href="/wiki/Data_structure" title="Data structure">data structure</a> that stores a collection of <a href="/wiki/Disjoint_sets" title="Disjoint sets">disjoint</a> (non-overlapping) <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">sets</a>. Equivalently, it stores a <a href="/wiki/Partition_of_a_set" title="Partition of a set">partition of a set</a> into disjoint <a href="/wiki/Subset" title="Subset">subsets</a>. It provides operations for adding new sets, merging sets (replacing them with their <a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a>), and finding a representative member of a set. The last operation makes it possible to determine efficiently whether any two elements belong to the same set or to different sets. </p><p>While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation known as a <b>disjoint-set forest</b>. This specialized type of <a href="/wiki/Forest_(graph_theory)" class="mw-redirect" title="Forest (graph theory)">forest</a> performs union and find operations in near-constant <a href="/wiki/Amortized_analysis" title="Amortized analysis">amortized time</a>. For a sequence of <span class="texhtml mvar" style="font-style:italic;">m</span> addition, union, or find operations on a disjoint-set forest with <span class="texhtml mvar" style="font-style:italic;">n</span> nodes, the total time required is <span class="texhtml"><a href="/wiki/Big_O_notation" title="Big O notation"><i>O</i></a>(<i>m</i>α(<i>n</i>))</span>, where <span class="texhtml">α(<i>n</i>)</span> is the extremely slow-growing <a href="/wiki/Inverse_Ackermann_function" class="mw-redirect" title="Inverse Ackermann function">inverse Ackermann function</a>. Although disjoint-set forests do not guarantee this time per operation, each operation rebalances the structure (via tree compression) so that subsequent operations become faster. As a result, disjoint-set forests are both <a href="/wiki/Asymptotically_optimal" class="mw-redirect" title="Asymptotically optimal">asymptotically optimal</a> and practically efficient. </p><p>Disjoint-set data structures play a key role in <a href="/wiki/Kruskal%27s_algorithm" title="Kruskal's algorithm">Kruskal's algorithm</a> for finding the <a href="/wiki/Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> of a graph. The importance of minimum spanning trees means that disjoint-set data structures support a wide variety of algorithms. In addition, these data structures find applications in symbolic computation and in compilers, especially for <a href="/wiki/Register_allocation" title="Register allocation">register allocation</a> problems. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="History">History</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=1" title="Edit section: History"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Disjoint-set forests were first described by <a href="/wiki/Bernard_A._Galler" class="mw-redirect" title="Bernard A. Galler">Bernard A. Galler</a> and <a href="/wiki/Michael_J._Fischer" title="Michael J. Fischer">Michael J. Fischer</a> in 1964.<sup id="cite_ref-Galler1964_2-0" class="reference"><a href="#cite_note-Galler1964-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> In 1973, their time complexity was bounded to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{*}(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log ^{*}(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6ad0ea4627a692443b1bffbddaacd44f3a4b46b9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.813ex; height:2.843ex;" alt="{\displaystyle O(\log ^{*}(n))}"></span>, the <a href="/wiki/Iterated_logarithm" title="Iterated logarithm">iterated logarithm</a> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>, by <a href="/wiki/John_Hopcroft" title="John Hopcroft">Hopcroft</a> and <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Ullman</a>.<sup id="cite_ref-Hopcroft1973_3-0" class="reference"><a href="#cite_note-Hopcroft1973-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> In 1975, <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Robert Tarjan</a> was the first to prove the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m\alpha (n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(m\alpha (n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e6ad711ac62a46c824c01e205f32a2fab557ceb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.315ex; height:2.843ex;" alt="{\displaystyle O(m\alpha (n))}"></span> (<a href="/wiki/Ackermann_function#Inverse" title="Ackermann function">inverse Ackermann function</a>) upper bound on the algorithm's time complexity,.<sup id="cite_ref-Tarjan1984_4-0" class="reference"><a href="#cite_note-Tarjan1984-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> He also proved it to be tight. In 1979, he showed that this was the lower bound for a certain class of algorithms, that include the Galler-Fischer structure.<sup id="cite_ref-Tarjan1979_5-0" class="reference"><a href="#cite_note-Tarjan1979-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> In 1989, <a href="/wiki/Michael_Fredman" title="Michael Fredman">Fredman</a> and <a href="/wiki/Michael_Saks_(mathematician)" title="Michael Saks (mathematician)">Saks</a> showed that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\alpha (n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Omega (\alpha (n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9bfdfd41667be083aff4b7c292a9f35884b654b8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.179ex; height:2.843ex;" alt="{\displaystyle \Omega (\alpha (n))}"></span> (amortized) words of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span> bits must be accessed by <i>any</i> disjoint-set data structure per operation,<sup id="cite_ref-Fredman1989_6-0" class="reference"><a href="#cite_note-Fredman1989-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> thereby proving the optimality of the data structure in this model. </p><p>In 1991, Galil and Italiano published a survey of data structures for disjoint-sets.<sup id="cite_ref-Galil1991_7-0" class="reference"><a href="#cite_note-Galil1991-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p><p>In 1994, Richard J. Anderson and Heather Woll described a parallelized version of Union–Find that never needs to block.<sup id="cite_ref-Anderson1994_8-0" class="reference"><a href="#cite_note-Anderson1994-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>In 2007, Sylvain Conchon and Jean-Christophe Filliâtre developed a semi-<a href="/wiki/Persistent_data_structure" title="Persistent data structure">persistent</a> version of the disjoint-set forest data structure and formalized its correctness using the <a href="/wiki/Proof_assistant" title="Proof assistant">proof assistant</a> <a href="/wiki/Coq_(software)" title="Coq (software)">Coq</a>.<sup id="cite_ref-Conchon2007_9-0" class="reference"><a href="#cite_note-Conchon2007-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> "Semi-persistent" means that previous versions of the structure are efficiently retained, but accessing previous versions of the data structure invalidates later ones. Their fastest implementation achieves performance almost as efficient as the non-persistent algorithm. They do not perform a complexity analysis. </p><p>Variants of disjoint-set data structures with better performance on a restricted class of problems have also been considered. Gabow and Tarjan showed that if the possible unions are restricted in certain ways, then a truly linear time algorithm is possible.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Representation">Representation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=2" title="Edit section: Representation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Each node in a disjoint-set forest consists of a pointer and some auxiliary information, either a size or a rank (but not both). The pointers are used to make <a href="/wiki/Parent_pointer_tree" title="Parent pointer tree">parent pointer trees</a>, where each node that is not the root of a tree points to its parent. To distinguish root nodes from others, their parent pointers have invalid values, such as a circular reference to the node or a sentinel value. Each tree represents a set stored in the forest, with the members of the set being the nodes in the tree. Root nodes provide set representatives: Two nodes are in the same set if and only if the roots of the trees containing the nodes are equal. </p><p>Nodes in the forest can be stored in any way convenient to the application, but a common technique is to store them in an array. In this case, parents can be indicated by their array index. Every array entry requires <span class="texhtml">Θ(log <i>n</i>)</span> bits of storage for the parent pointer. A comparable or lesser amount of storage is required for the rest of the entry, so the number of bits required to store the forest is <span class="texhtml">Θ(<i>n</i> log <i>n</i>)</span>. If an implementation uses fixed size nodes (thereby limiting the maximum size of the forest that can be stored), then the necessary storage is linear in <span class="texhtml mvar" style="font-style:italic;">n</span>. </p> <div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=3" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Disjoint-set data structures support three operations: Making a new set containing a new element; Finding the representative of the set containing a given element; and Merging two sets. </p> <div class="mw-heading mw-heading3"><h3 id="Making_new_sets">Making new sets</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=4" title="Edit section: Making new sets"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <code>MakeSet</code> operation adds a new element into a new set containing only the new element, and the new set is added to the data structure. If the data structure is instead viewed as a partition of a set, then the <code>MakeSet</code> operation enlarges the set by adding the new element, and it extends the existing partition by putting the new element into a new subset containing only the new element. </p><p>In a disjoint-set forest, <code>MakeSet</code> initializes the node's parent pointer and the node's size or rank. If a root is represented by a node that points to itself, then adding an element can be described using the following pseudocode: </p> <pre><b>function</b> MakeSet(<i>x</i>) <b>is</b> <b>if</b> <i>x</i> is not already in the forest <b>then</b> <i>x</i>.parent := <i>x</i> <i>x</i>.size := 1 <i>// if nodes store size</i> <i>x</i>.rank := 0 <i>// if nodes store rank</i> <b>end if</b> <b>end function</b> </pre> <p>This operation has linear time complexity. In particular, initializing a disjoint-set forest with <span class="texhtml mvar" style="font-style:italic;">n</span> nodes requires <span class="texhtml"><i>O</i>(<i>n</i>)</span> time. </p><p>Lack of a parent assigned to the node implies that the node is not present in the forest. </p><p>In practice, <code>MakeSet</code> must be preceded by an operation that allocates memory to hold <span class="texhtml">x</span>. As long as memory allocation is an amortized constant-time operation, as it is for a good <a href="/wiki/Dynamic_array" title="Dynamic array">dynamic array</a> implementation, it does not change the asymptotic performance of the random-set forest. </p> <div class="mw-heading mw-heading3"><h3 id="Finding_set_representatives">Finding set representatives</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=5" title="Edit section: Finding set representatives"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <code>Find</code> operation follows the chain of parent pointers from a specified query node <span class="texhtml mvar" style="font-style:italic;">x</span> until it reaches a root element. This root element represents the set to which <span class="texhtml mvar" style="font-style:italic;">x</span> belongs and may be <span class="texhtml mvar" style="font-style:italic;">x</span> itself. <code>Find</code> returns the root element it reaches. </p><p>Performing a <code>Find</code> operation presents an important opportunity for improving the forest. The time in a <code>Find</code> operation is spent chasing parent pointers, so a flatter tree leads to faster <code>Find</code> operations. When a <code>Find</code> is executed, there is no faster way to reach the root than by following each parent pointer in succession. However, the parent pointers visited during this search can be updated to point closer to the root. Because every element visited on the way to a root is part of the same set, this does not change the sets stored in the forest. But it makes future <code>Find</code> operations faster, not only for the nodes between the query node and the root, but also for their descendants. This updating is an important part of the disjoint-set forest's amortized performance guarantee. </p><p>There are several algorithms for <code>Find</code> that achieve the asymptotically optimal time complexity. One family of algorithms, known as <b>path compression</b>, makes every node between the query node and the root point to the root. Path compression can be implemented using a simple recursion as follows: </p> <pre><b>function</b> Find(<i>x</i>) <b>is</b> <b>if</b> <i>x</i>.parent ≠ <i>x</i> <b>then</b> <i>x</i>.parent := Find(<i>x</i>.parent) <b>return</b> <i>x</i>.parent <b>else</b> <b>return</b> <i>x</i> <b>end if</b> <b>end function</b> </pre> <p>This implementation makes two passes, one up the tree and one back down. It requires enough scratch memory to store the path from the query node to the root (in the above pseudocode, the path is implicitly represented using the call stack). This can be decreased to a constant amount of memory by performing both passes in the same direction. The constant memory implementation walks from the query node to the root twice, once to find the root and once to update pointers: </p> <pre><b>function</b> Find(<i>x</i>) <b>is</b> <i>root</i> := <i>x</i> <b>while</b> <i>root</i>.parent ≠ <i>root</i> <b>do</b> <i>root</i> := <i>root</i>.parent <b>end while</b> <b>while</b> <i>x</i>.parent ≠ <i>root</i> <b>do</b> <i>parent</i> := <i>x</i>.parent <i>x</i>.parent := <i>root</i> <i>x</i> := <i>parent</i> <b>end while</b> <b>return</b> <i>root</i> <b>end function</b> </pre> <p><a href="/wiki/Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Tarjan</a> and <a href="/wiki/Jan_van_Leeuwen" title="Jan van Leeuwen">Van Leeuwen</a> also developed one-pass <code>Find</code> algorithms that retain the same worst-case complexity but are more efficient in practice.<sup id="cite_ref-Tarjan1984_4-1" class="reference"><a href="#cite_note-Tarjan1984-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> These are called path splitting and path halving. Both of these update the parent pointers of nodes on the path between the query node and the root. <b>Path splitting</b> replaces every parent pointer on that path by a pointer to the node's grandparent: </p> <pre><b>function</b> Find(<i>x</i>) <b>is</b> <b>while</b> <i>x</i>.parent ≠ <i>x</i> <b>do</b> (<i>x</i>, <i>x</i>.parent) := (<i>x</i>.parent, <i>x</i>.parent.parent) <b>end while</b> <b>return</b> <i>x</i> <b>end function</b> </pre> <p><b>Path halving</b> works similarly but replaces only every other parent pointer: </p> <pre><b>function</b> Find(<i>x</i>) <b>is</b> <b>while</b> <i>x</i>.parent ≠ <i>x</i> <b>do</b> <i>x</i>.parent := <i>x</i>.parent.parent <i>x</i> := <i>x</i>.parent <b>end while</b> <b>return</b> <i>x</i> <b>end function</b> </pre> <div class="mw-heading mw-heading3"><h3 id="Merging_two_sets">Merging two sets</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=6" title="Edit section: Merging two sets"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Dsu_disjoint_sets_init.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/67/Dsu_disjoint_sets_init.svg/360px-Dsu_disjoint_sets_init.svg.png" decoding="async" width="360" height="33" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/67/Dsu_disjoint_sets_init.svg/540px-Dsu_disjoint_sets_init.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/67/Dsu_disjoint_sets_init.svg/720px-Dsu_disjoint_sets_init.svg.png 2x" data-file-width="440" data-file-height="40" /></a><figcaption><code>MakeSet</code> creates 8 singletons.</figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Dsu_disjoint_sets_final.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Dsu_disjoint_sets_final.svg/360px-Dsu_disjoint_sets_final.svg.png" decoding="async" width="360" height="33" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Dsu_disjoint_sets_final.svg/540px-Dsu_disjoint_sets_final.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/ac/Dsu_disjoint_sets_final.svg/720px-Dsu_disjoint_sets_final.svg.png 2x" data-file-width="440" data-file-height="40" /></a><figcaption>After some operations of <code>Union</code>, some sets are grouped together.</figcaption></figure> <p>The operation <code>Union(<i>x</i>, <i>y</i>)</code> replaces the set containing <span class="texhtml mvar" style="font-style:italic;">x</span> and the set containing <span class="texhtml mvar" style="font-style:italic;">y</span> with their union. <code>Union</code> first uses <code>Find</code> to determine the roots of the trees containing <span class="texhtml mvar" style="font-style:italic;">x</span> and <span class="texhtml mvar" style="font-style:italic;">y</span>. If the roots are the same, there is nothing more to do. Otherwise, the two trees must be merged. This is done by either setting the parent pointer of <span class="texhtml mvar" style="font-style:italic;">x</span>'s root to <span class="texhtml mvar" style="font-style:italic;">y</span>'s, or setting the parent pointer of <span class="texhtml mvar" style="font-style:italic;">y</span>'s root to <span class="texhtml mvar" style="font-style:italic;">x</span>'s. </p><p>The choice of which node becomes the parent has consequences for the complexity of future operations on the tree. If it is done carelessly, trees can become excessively tall. For example, suppose that <code>Union</code> always made the tree containing <span class="texhtml mvar" style="font-style:italic;">x</span> a subtree of the tree containing <span class="texhtml mvar" style="font-style:italic;">y</span>. Begin with a forest that has just been initialized with elements <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,2,3,\ldots ,n,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1,2,3,\ldots ,n,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5a3d8fe63a83d104e561694135d73b64ec3c6fb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.775ex; height:2.509ex;" alt="{\displaystyle 1,2,3,\ldots ,n,}"></span> and execute <code><span class="texhtml">Union(1, 2)</span></code>, <code><span class="texhtml">Union(2, 3)</span></code>, ..., <code><span class="texhtml">Union(<i>n</i> - 1, <i>n</i>)</span></code>. The resulting forest contains a single tree whose root is <span class="texhtml mvar" style="font-style:italic;">n</span>, and the path from 1 to <span class="texhtml mvar" style="font-style:italic;">n</span> passes through every node in the tree. For this forest, the time to run <code>Find(1)</code> is <span class="texhtml"><i>O</i>(<i>n</i>)</span>. </p><p>In an efficient implementation, tree height is controlled using <b>union by size</b> or <b>union by rank</b>. Both of these require a node to store information besides just its parent pointer. This information is used to decide which root becomes the new parent. Both strategies ensure that trees do not become too deep. </p> <div class="mw-heading mw-heading4"><h4 id="Union_by_size">Union by size</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=7" title="Edit section: Union by size"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the case of union by size, a node stores its size, which is simply its number of descendants (including the node itself). When the trees with roots <span class="texhtml mvar" style="font-style:italic;">x</span> and <span class="texhtml mvar" style="font-style:italic;">y</span> are merged, the node with more descendants becomes the parent. If the two nodes have the same number of descendants, then either one can become the parent. In both cases, the size of the new parent node is set to its new total number of descendants. </p> <pre><b>function</b> Union(<i>x</i>, <i>y</i>) <b>is</b> <i>// Replace nodes by roots</i> <i>x</i> := Find(<i>x</i>) <i>y</i> := Find(<i>y</i>) <b>if</b> <i>x</i> = <i>y</i> <b>then</b> <b>return</b> <i>// x and y are already in the same set</i> <b>end if</b> <i>// If necessary, swap variables to ensure that</i> <i>// x has at least as many descendants as y</i> <b>if</b> <i>x</i>.size < <i>y</i>.size <b>then</b> (<i>x</i>, <i>y</i>) := (<i>y</i>, <i>x</i>) <b>end if</b> <i>// Make x the new root</i> <i>y</i>.parent := <i>x</i> <i>// Update the size of x</i> <i>x</i>.size := <i>x</i>.size + <i>y</i>.size <b>end function</b> </pre> <p>The number of bits necessary to store the size is clearly the number of bits necessary to store <span class="texhtml mvar" style="font-style:italic;">n</span>. This adds a constant factor to the forest's required storage. </p> <div class="mw-heading mw-heading4"><h4 id="Union_by_rank">Union by rank</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=8" title="Edit section: Union by rank"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For union by rank, a node stores its <em>rank</em>, which is an upper bound for its height. When a node is initialized, its rank is set to zero. To merge trees with roots <span class="texhtml mvar" style="font-style:italic;">x</span> and <span class="texhtml mvar" style="font-style:italic;">y</span>, first compare their ranks. If the ranks are different, then the larger rank tree becomes the parent, and the ranks of <span class="texhtml mvar" style="font-style:italic;">x</span> and <span class="texhtml mvar" style="font-style:italic;">y</span> do not change. If the ranks are the same, then either one can become the parent, but the new parent's rank is incremented by one. While the rank of a node is clearly related to its height, storing ranks is more efficient than storing heights. The height of a node can change during a <code>Find</code> operation, so storing ranks avoids the extra effort of keeping the height correct. In pseudocode, union by rank is: </p> <pre><b>function</b> Union(<i>x</i>, <i>y</i>) <b>is</b> <i>// Replace nodes by roots</i> <i>x</i> := Find(<i>x</i>) <i>y</i> := Find(<i>y</i>) <b>if</b> <i>x</i> = <i>y</i> <b>then</b> <b>return</b> <i>// x and y are already in the same set</i> <b>end if</b> <i>// If necessary, rename variables to ensure that</i> <i>// x has rank at least as large as that of y</i> <b>if</b> <i>x</i>.rank < <i>y</i>.rank <b>then</b> (<i>x</i>, <i>y</i>) := (<i>y</i>, <i>x</i>) <b>end if</b> <i>// Make x the new root</i> <i>y</i>.parent := <i>x</i> <i>// If necessary, increment the rank of x</i> <b>if</b> <i>x</i>.rank = <i>y</i>.rank <b>then</b> <i>x</i>.rank := <i>x</i>.rank + 1 <b>end if</b> <b>end function</b> </pre> <p>It can be shown that every node has rank <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor \log n\rfloor }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌊</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo fence="false" stretchy="false">⌋</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lfloor \log n\rfloor }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2691a5620da37c1f740a04a8fd226072143455c9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.818ex; height:2.843ex;" alt="{\displaystyle \lfloor \log n\rfloor }"></span> or less.<sup id="cite_ref-Cormen2009_11-0" class="reference"><a href="#cite_note-Cormen2009-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Consequently each rank can be stored in <span class="texhtml"><i>O</i>(log log <i>n</i>)</span> bits and all the ranks can be stored in <span class="texhtml"><i>O</i>(<i>n</i> log log <i>n</i>)</span> bits. This makes the ranks an asymptotically negligible portion of the forest's size. </p><p>It is clear from the above implementations that the size and rank of a node do not matter unless a node is the root of a tree. Once a node becomes a child, its size and rank are never accessed again. </p> <div class="mw-heading mw-heading2"><h2 id="Time_complexity">Time complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=9" title="Edit section: Time complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A disjoint-set forest implementation in which <code>Find</code> does not update parent pointers, and in which <code>Union</code> does not attempt to control tree heights, can have trees with height <span class="texhtml"><i>O</i>(<i>n</i>)</span>. In such a situation, the <code>Find</code> and <code>Union</code> operations require <span class="texhtml"><i>O</i>(<i>n</i>)</span> time. </p><p>If an implementation uses path compression alone, then a sequence of <span class="texhtml mvar" style="font-style:italic;">n</span> <code>MakeSet</code> operations, followed by up to <span class="texhtml"><i>n</i> − 1</span> <code>Union</code> operations and <span class="texhtml"><i>f</i></span> <code>Find</code> operations, has a worst-case running time of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>f</mi> <mo>⋅</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>+</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo>+</mo> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mrow> </msub> <mo>⁡</mo> <mi>n</mi> </mrow> <mo>)</mo> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6e209b18c4cd57bd8f29a3d84d3911a9c708155e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:26.742ex; height:3.343ex;" alt="{\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}"></span>.<sup id="cite_ref-Cormen2009_11-1" class="reference"><a href="#cite_note-Cormen2009-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p><p>Using union by rank, but without updating parent pointers during <code>Find</code>, gives a running time of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (m\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (m\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1dc4a519eddba0d1d9242936a7ca0422c3f33a30" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.798ex; height:2.843ex;" alt="{\displaystyle \Theta (m\log n)}"></span> for <span class="texhtml mvar" style="font-style:italic;">m</span> operations of any type, up to <span class="texhtml mvar" style="font-style:italic;">n</span> of which are <code>MakeSet</code> operations.<sup id="cite_ref-Cormen2009_11-2" class="reference"><a href="#cite_note-Cormen2009-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p><p>The combination of path compression, splitting, or halving, with union by size or by rank, reduces the running time for <span class="texhtml mvar" style="font-style:italic;">m</span> operations of any type, up to <span class="texhtml mvar" style="font-style:italic;">n</span> of which are <code>MakeSet</code> operations, to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (m\alpha (n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (m\alpha (n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ef73db523155adccdb88ef38828472de6c31294" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.349ex; height:2.843ex;" alt="{\displaystyle \Theta (m\alpha (n))}"></span>.<sup id="cite_ref-Tarjan1984_4-2" class="reference"><a href="#cite_note-Tarjan1984-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Tarjan1979_5-1" class="reference"><a href="#cite_note-Tarjan1979-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> This makes the <a href="/wiki/Amortized_analysis" title="Amortized analysis">amortized running time</a> of each operation <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (\alpha (n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (\alpha (n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc86ca978bb6d4e7a6c466ec8829a0010c968982" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.309ex; height:2.843ex;" alt="{\displaystyle \Theta (\alpha (n))}"></span>. This is asymptotically optimal, meaning that every disjoint set data structure must use <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\alpha (n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Omega (\alpha (n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9bfdfd41667be083aff4b7c292a9f35884b654b8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.179ex; height:2.843ex;" alt="{\displaystyle \Omega (\alpha (n))}"></span> amortized time per operation.<sup id="cite_ref-Fredman1989_6-1" class="reference"><a href="#cite_note-Fredman1989-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Here, the function <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha (n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha (n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/74c1642d9e2f86b9e5c86c0f18ee5377507da827" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.692ex; height:2.843ex;" alt="{\displaystyle \alpha (n)}"></span> is the <a href="/wiki/Ackermann_function#Inverse" title="Ackermann function">inverse Ackermann function</a>. The inverse Ackermann function grows extraordinarily slowly, so this factor is <span class="texhtml">4</span> or less for any <span class="texhtml mvar" style="font-style:italic;">n</span> that can actually be written in the physical universe. This makes disjoint-set operations practically amortized constant time. </p> <div class="mw-heading mw-heading3"><h3 id="Proof_of_O(m_log*_n)_time_complexity_of_Union-Find"><span id="Proof_of_O.28m_log.2A_n.29_time_complexity_of_Union-Find"></span>Proof of O(m log* n) time complexity of Union-Find</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=10" title="Edit section: Proof of O(m log* n) time complexity of Union-Find"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any <span class="texhtml mvar" style="font-style:italic;">m</span> <code>Find</code> or <code>Union</code> operations on a disjoint-set forest containing <span class="texhtml mvar" style="font-style:italic;">n</span> objects is <span class="texhtml"><i>O</i>(<i>m</i> log<sup>*</sup> <i>n</i>)</span>, where <span class="texhtml">log<sup>*</sup></span> denotes the <a href="/wiki/Iterated_logarithm" title="Iterated logarithm">iterated logarithm</a>.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p><p><span class="anchor" id="increasing_rank_lemma"></span>Lemma 1: As the <a href="#Disjoint-set_forests">find function</a> follows the path along to the root, the rank of node it encounters is increasing. </p> <style data-mw-deduplicate="TemplateStyles:r1174254338">.mw-parser-output .math_proof{border:thin solid #aaa;margin:1em 2em;padding:0.5em 1em 0.4em}@media(max-width:500px){.mw-parser-output .math_proof{margin:1em 0;padding:0.5em 0.5em 0.4em}}</style><div class="math_proof" style=""><strong>Proof</strong> <p>We claim that as Find and Union operations are applied to the data set, this fact remains true over time. Initially when each node is the root of its own tree, it's trivially true. The only case when the rank of a node might be changed is when the <a href="#Disjoint-set_forests">Union by Rank</a> operation is applied. In this case, a tree with smaller rank will be attached to a tree with greater rank, rather than vice versa. And during the find operation, all nodes visited along the path will be attached to the root, which has larger rank than its children, so this operation won't change this fact either. </p> </div> <p><span class="anchor" id="min_subtree_size_lemma"></span>Lemma 2: A node <span class="texhtml mvar" style="font-style:italic;">u</span> which is root of a subtree with rank <span class="texhtml mvar" style="font-style:italic;">r</span> has at least <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7f5f9125e1c1d0ac48d810ee16bfe95c6dabcad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.136ex; height:2.343ex;" alt="{\displaystyle 2^{r}}"></span> nodes. </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1174254338"><div class="math_proof" style=""><strong>Proof</strong> <p>Initially when each node is the root of its own tree, it's trivially true. Assume that a node <span class="texhtml mvar" style="font-style:italic;">u</span> with rank <span class="texhtml mvar" style="font-style:italic;">r</span> has at least <span class="texhtml">2<sup><i>r</i></sup></span> nodes. Then when two trees with rank <span class="texhtml mvar" style="font-style:italic;">r</span> are merged using the operation <a href="#Disjoint-set_forests">Union by Rank</a>, a tree with rank <span class="texhtml"><i>r</i> + 1</span> results, the root of which has at least <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r}+2^{r}=2^{r+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> <mo>+</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{r}+2^{r}=2^{r+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b3f050b8962a385242f91c28ff7dc16835c1a7a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.448ex; height:2.843ex;" alt="{\displaystyle 2^{r}+2^{r}=2^{r+1}}"></span> nodes. </p> </div> <figure class="mw-default-size mw-halign-center" typeof="mw:File"><a href="/wiki/File:ProofOflogstarnRank.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/en/4/4d/ProofOflogstarnRank.jpg" decoding="async" width="313" height="302" class="mw-file-element" data-file-width="313" data-file-height="302" /></a><figcaption></figcaption></figure> <p>Lemma 3: The maximum number of nodes of rank <span class="texhtml mvar" style="font-style:italic;">r</span> is at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2^{r}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2^{r}}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/73c408491edd68f7fceefc447ecccdb2919423b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:3.619ex; height:4.843ex;" alt="{\displaystyle {\frac {n}{2^{r}}}.}"></span> </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1174254338"><div class="math_proof" style=""><strong>Proof</strong> <p>From <a href="#min_subtree_size_lemma">lemma 2</a>, we know that a node <span class="texhtml mvar" style="font-style:italic;">u</span> which is root of a subtree with rank <span class="texhtml mvar" style="font-style:italic;">r</span> has at least <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7f5f9125e1c1d0ac48d810ee16bfe95c6dabcad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.136ex; height:2.343ex;" alt="{\displaystyle 2^{r}}"></span> nodes. We will get the maximum number of nodes of rank <span class="texhtml mvar" style="font-style:italic;">r</span> when each node with rank <span class="texhtml mvar" style="font-style:italic;">r</span> is the root of a tree that has exactly <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7f5f9125e1c1d0ac48d810ee16bfe95c6dabcad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.136ex; height:2.343ex;" alt="{\displaystyle 2^{r}}"></span> nodes. In this case, the number of nodes of rank <span class="texhtml mvar" style="font-style:italic;">r</span> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2^{r}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2^{r}}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/73c408491edd68f7fceefc447ecccdb2919423b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:3.619ex; height:4.843ex;" alt="{\displaystyle {\frac {n}{2^{r}}}.}"></span> </p> </div> <p>At any particular point in the execution, we can group the vertices of the graph into "buckets", according to their rank. We define the buckets' ranges inductively, as follows: Bucket 0 contains vertices of rank 0. Bucket 1 contains vertices of rank 1. Bucket 2 contains vertices of ranks 2 and 3. In general, if the <span class="texhtml mvar" style="font-style:italic;">B</span>-th bucket contains vertices with ranks from interval <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>[</mo> <mrow> <mi>r</mi> <mo>,</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> <mo>]</mo> </mrow> <mo>=</mo> <mo stretchy="false">[</mo> <mi>r</mi> <mo>,</mo> <mi>R</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49aa6ca95d184c363386c5c5aaa6c8932934e9b2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.757ex; height:2.843ex;" alt="{\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}"></span>, then the (B+1)st bucket will contain vertices with ranks from interval <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left[R,2^{R}-1\right].}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>[</mo> <mrow> <mi>R</mi> <mo>,</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> <mo>]</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left[R,2^{R}-1\right].}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe254e2d62c18dbe3ed168f4417653d5afd1ed23" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.416ex; height:3.343ex;" alt="{\displaystyle \left[R,2^{R}-1\right].}"></span> </p><p><br /> For <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\in \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B\in \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b61c9034faef7d7729254ebfc51ce247955a165" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.283ex; height:2.176ex;" alt="{\displaystyle B\in \mathbb {N} }"></span>, let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>tower</mtext> </mrow> <mo stretchy="false">(</mo> <mi>B</mi> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mrow class="MJX-TeXAtom-OP MJX-fixedlimits"> <munder> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msup> <mo>⋯</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </msup> </mrow> </msup> <mo>⏟</mo> </munder> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> times</mtext> </mrow> </mrow> </munder> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2db06cffcc90a9f0c2ab78e90eb36c40e8219ae6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:18.033ex; height:6.843ex;" alt="{\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}"></span>. Then bucket <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span> will have vertices with ranks in the interval <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [{\text{tower}}(B-1),{\text{tower}}(B)-1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>tower</mtext> </mrow> <mo stretchy="false">(</mo> <mi>B</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>tower</mtext> </mrow> <mo stretchy="false">(</mo> <mi>B</mi> <mo stretchy="false">)</mo> <mo>−</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [{\text{tower}}(B-1),{\text{tower}}(B)-1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ef0146c95ec30ab5e27b2ea4d6925435b79595de" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.858ex; height:2.843ex;" alt="{\displaystyle [{\text{tower}}(B-1),{\text{tower}}(B)-1]}"></span>. </p> <figure class="mw-halign-center" typeof="mw:File/Frame"><a href="/wiki/File:Proof_of_O(log*n)_Union_Find.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/d/d5/Proof_of_O%28log%2An%29_Union_Find.jpg" decoding="async" width="556" height="261" class="mw-file-element" data-file-width="556" data-file-height="261" /></a><figcaption>Proof of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{*}n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log ^{*}n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba846ca61ce56540d44c487534367163945ad17d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.39ex; height:2.843ex;" alt="{\displaystyle O(\log ^{*}n)}"></span> Union Find</figcaption></figure> <p>We can make two observations about the buckets' sizes. </p> <ol><li><span class="anchor" id="max_buckets"></span>The total number of buckets is at most <span class="texhtml">log<sup>*</sup><i>n</i></span>. <dl><dd>Proof: Since no vertex can have rank greater than <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>, only the first <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log ^{*}(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log ^{*}(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf706147043580232b6e19d25c80a0f73bb2d525" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.23ex; height:2.843ex;" alt="{\displaystyle \log ^{*}(n)}"></span> buckets can have vertices, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log ^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log ^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e19ae183e78de19eeba18aa7281720cedf5e620b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.026ex; height:2.676ex;" alt="{\displaystyle \log ^{*}}"></span> denotes the inverse of the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{tower}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>tower</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{tower}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/513308f09a89c4c867fe9478a2046cfb311a6595" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.689ex; height:2.009ex;" alt="{\displaystyle {\text{tower}}}"></span> function defined above.</dd></dl></li> <li><span class="anchor" id="max_bucket_size"></span>The maximum number of elements in bucket <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left[B,2^{B}-1\right]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>[</mo> <mrow> <mi>B</mi> <mo>,</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left[B,2^{B}-1\right]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70d4053472d64e0df71dcc2afcd0a3612a0d0ec8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.382ex; height:3.343ex;" alt="{\displaystyle \left[B,2^{B}-1\right]}"></span> is at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {2n}{2^{B}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {2n}{2^{B}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b683d9326a268636904f987d7790ac7411659770" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:3.478ex; height:5.676ex;" alt="{\displaystyle {\frac {2n}{2^{B}}}}"></span>. <dl><dd>Proof: The maximum number of elements in bucket <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left[B,2^{B}-1\right]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>[</mo> <mrow> <mi>B</mi> <mo>,</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left[B,2^{B}-1\right]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70d4053472d64e0df71dcc2afcd0a3612a0d0ec8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.382ex; height:3.343ex;" alt="{\displaystyle \left[B,2^{B}-1\right]}"></span> is at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> </mfrac> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </mfrac> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> <mo>+</mo> <mn>2</mn> </mrow> </msup> </mfrac> </mrow> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mfrac> </mrow> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63c4bd9a5b92a47caf6fc4cad79021fe08f0da86" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:42.274ex; height:6.009ex;" alt="{\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}"></span></dd></dl></li></ol> <p>Let <span class="texhtml mvar" style="font-style:italic;">F</span> represent the list of "find" operations performed, and let </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>F</mi> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mtext>(link to the root)</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46d02c8c920e47add454150f29940618341b2c0a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:26.055ex; height:5.509ex;" alt="{\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>F</mi> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mtext>(number of links traversed where the buckets are different)</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/15dc94f376bdb48b3ad7d1dd1f6efc7e6bb64939" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:67.978ex; height:5.509ex;" alt="{\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>F</mi> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mtext>(number of links traversed where the buckets are the same).</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e51e81e137aeca61ba3174dbeb6f55ee6f84046" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:68.945ex; height:5.509ex;" alt="{\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}"></span> </p><p>Then the total cost of <span class="texhtml mvar" style="font-style:italic;">m</span> finds is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=T_{1}+T_{2}+T_{3}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>=</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T=T_{1}+T_{2}+T_{3}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e3ff11b91349544dee273c5d937271b0cb613be5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.298ex; height:2.509ex;" alt="{\displaystyle T=T_{1}+T_{2}+T_{3}.}"></span> </p><p>Since each find operation makes exactly one traversal that leads to a root, we have <span class="texhtml"><i>T</i><sub>1</sub> = <i>O</i>(<i>m</i>)</span>. </p><p>Also, from the bound above on the number of buckets, we have <span class="texhtml"><i>T</i><sub>2</sub> = <i>O</i>(<i>m</i>log<sup>*</sup><i>n</i>)</span>. </p><p>For <span class="texhtml mvar" style="font-style:italic;">T<sub>3</sub></span>, suppose we are traversing an edge from <span class="texhtml mvar" style="font-style:italic;">u</span> to <span class="texhtml mvar" style="font-style:italic;">v</span>, where <span class="texhtml mvar" style="font-style:italic;">u</span> and <span class="texhtml mvar" style="font-style:italic;">v</span> have rank in the bucket <span class="texhtml">[<i>B</i>, 2<sup><i>B</i></sup> − 1]</span> and <span class="texhtml mvar" style="font-style:italic;">v</span> is not the root (at the time of this traversing, otherwise the traversal would be accounted for in <span class="texhtml mvar" style="font-style:italic;">T<sub>1</sub></span>). Fix <span class="texhtml mvar" style="font-style:italic;">u</span> and consider the sequence <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1},v_{2},\ldots ,v_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{1},v_{2},\ldots ,v_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f4cea5f36d7a84bb76f2dc891a9498d856b2851" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.792ex; height:2.009ex;" alt="{\displaystyle v_{1},v_{2},\ldots ,v_{k}}"></span> that take the role of <span class="texhtml mvar" style="font-style:italic;">v</span> in different find operations. Because of path compression and not accounting for the edge to a root, this sequence contains only different nodes and because of <a href="#increasing_rank_lemma">Lemma 1</a> we know that the ranks of the nodes in this sequence are strictly increasing. By both of the nodes being in the bucket we can conclude that the length <span class="texhtml mvar" style="font-style:italic;">k</span> of the sequence (the number of times node <span class="texhtml mvar" style="font-style:italic;">u</span> is attached to a different root in the same bucket) is at most the number of ranks in the buckets <span class="texhtml mvar" style="font-style:italic;">B</span>, that is, at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{B}-1-B<2^{B}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> <mo>−</mo> <mi>B</mi> <mo><</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{B}-1-B<2^{B}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/db28624639513ee601384d1ebe7774e1c2a50d86" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:17.637ex; height:2.843ex;" alt="{\displaystyle 2^{B}-1-B<2^{B}.}"></span> </p><p>Therefore, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>≤</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">[</mo> <mi>B</mi> <mo>,</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mrow> </munder> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>u</mi> </mrow> </munder> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6f85cd493fd0596a25595537c645fc839d9ebf0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:19.647ex; height:6.343ex;" alt="{\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}"></span> </p><p>From Observations <a href="#max_buckets">1</a> and <a href="#max_bucket_size">2</a>, we can conclude that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>≤</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </munder> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> </mfrac> </mrow> <mo>≤</mo> <mn>2</mn> <mi>n</mi> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>⁡</mo> <mi>n</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bae8a83684fb38b41e393d1edd84e3488873a1c5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:27.805ex; height:4.009ex;" alt="{\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}"></span> </p><p>Therefore, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo>=</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <msup> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49c0ecafaa451f4f32aed4a06035feb3797777a3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.214ex; height:2.843ex;" alt="{\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}"></span> </p> <div class="mw-heading mw-heading2"><h2 id="Other_structures">Other structures</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=11" title="Edit section: Other structures"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Better_worst-case_time_per_operation">Better worst-case time per operation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=12" title="Edit section: Better worst-case time per operation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The worst-case time of the <code>Find</code> operation in trees with <b>Union by rank</b> or <b>Union by weight</b> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Theta (\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65bac5223de9c91eb3e89a032b5c51fd3041dc66" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.371ex; height:2.843ex;" alt="{\displaystyle \Theta (\log n)}"></span> (i.e., it is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span> and this bound is tight). In 1985, N. Blum gave an implementation of the operations that does not use path compression, but compresses trees during <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle union}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mi>n</mi> <mi>i</mi> <mi>o</mi> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle union}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6c47ba3e46bce1b4aefaabf75f8b0036161820a7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.049ex; height:2.176ex;" alt="{\displaystyle union}"></span>. His implementation runs in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n/\log \log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n/\log \log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc17efd2d66135a2972e35ab7680ec720efc8d5b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.998ex; height:2.843ex;" alt="{\displaystyle O(\log n/\log \log n)}"></span> time per operation,<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> and thus in comparison with Galler and Fischer's structure it has a better worst-case time per operation, but inferior amortized time. In 1999, Alstrup et al. gave a structure that has optimal worst-case time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n/\log \log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n/\log \log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc17efd2d66135a2972e35ab7680ec720efc8d5b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.998ex; height:2.843ex;" alt="{\displaystyle O(\log n/\log \log n)}"></span> together with inverse-Ackermann amortized time.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Deletion">Deletion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=13" title="Edit section: Deletion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The regular implementation as disjoint-set forests does not react favorably to the deletion of elements, in the sense that the time for <code>Find</code> will not improve as a result of the decrease in the number of elements. However, there exist modern implementations that allow for constant-time deletion and where the time-bound for <code>Find</code> depends on the <i>current</i> number of elements<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=14" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:UnionFindKruskalDemo.gif" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a3/UnionFindKruskalDemo.gif/250px-UnionFindKruskalDemo.gif" decoding="async" width="250" height="353" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a3/UnionFindKruskalDemo.gif/375px-UnionFindKruskalDemo.gif 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a3/UnionFindKruskalDemo.gif/500px-UnionFindKruskalDemo.gif 2x" data-file-width="744" data-file-height="1052" /></a><figcaption>A demo for Union-Find when using Kruskal's algorithm to find minimum spanning tree.</figcaption></figure> <p>Disjoint-set data structures model the <a href="/wiki/Partition_of_a_set" title="Partition of a set">partitioning of a set</a>, for example to keep track of the <a href="/wiki/Connected_component_(graph_theory)" class="mw-redirect" title="Connected component (graph theory)">connected components</a> of an <a href="/wiki/Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a>. This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle. The Union–Find algorithm is used in high-performance implementations of <a href="/wiki/Unification_(computer_science)" title="Unification (computer science)">unification</a>.<sup id="cite_ref-Knight1989_20-0" class="reference"><a href="#cite_note-Knight1989-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> </p><p>This data structure is used by the <a href="/wiki/Boost_Graph_Library" class="mw-redirect" title="Boost Graph Library">Boost Graph Library</a> to implement its <a rel="nofollow" class="external text" href="http://www.boost.org/libs/graph/doc/incremental_components.html">Incremental Connected Components</a> functionality. It is also a key component in implementing <a href="/wiki/Kruskal%27s_algorithm" title="Kruskal's algorithm">Kruskal's algorithm</a> to find the <a href="/wiki/Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> of a graph. </p><p>The <a href="/wiki/Hoshen%E2%80%93Kopelman_algorithm" title="Hoshen–Kopelman algorithm">Hoshen-Kopelman algorithm</a> uses a Union-Find in the algorithm. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=15" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Partition_refinement" title="Partition refinement">Partition refinement</a>, a different data structure for maintaining disjoint sets, with updates that split sets apart rather than merging them together</li> <li><a href="/wiki/Dynamic_connectivity" title="Dynamic connectivity">Dynamic connectivity</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=16" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-tarjan1975-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-tarjan1975_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-tarjan1975_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-tarjan1975_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-tarjan1975_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-tarjan1975_1-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-tarjan1975_1-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFTarjan1975" class="citation journal cs1"><a href="/wiki/Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Tarjan, Robert Endre</a> (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". <i>Journal of the ACM</i>. <b>22</b> (2): <span class="nowrap">215–</span>225. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321879.321884">10.1145/321879.321884</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F5942">1813/5942</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11105749">11105749</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Efficiency+of+a+Good+But+Not+Linear+Set+Union+Algorithm&rft.volume=22&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E215-%3C%2Fspan%3E225&rft.date=1975&rft_id=info%3Ahdl%2F1813%2F5942&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11105749%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F321879.321884&rft.aulast=Tarjan&rft.aufirst=Robert+Endre&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Galler1964-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Galler1964_2-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGallerFischer1964" class="citation journal cs1"><a href="/wiki/Bernard_A._Galler" class="mw-redirect" title="Bernard A. Galler">Galler, Bernard A.</a>; <a href="/wiki/Michael_J._Fischer" title="Michael J. Fischer">Fischer, Michael J.</a> (May 1964). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F364099.364331">"An improved equivalence algorithm"</a>. <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>. <b>7</b> (5): <span class="nowrap">301–</span>303. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F364099.364331">10.1145/364099.364331</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9034016">9034016</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=An+improved+equivalence+algorithm&rft.volume=7&rft.issue=5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E301-%3C%2Fspan%3E303&rft.date=1964-05&rft_id=info%3Adoi%2F10.1145%2F364099.364331&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A9034016%23id-name%3DS2CID&rft.aulast=Galler&rft.aufirst=Bernard+A.&rft.au=Fischer%2C+Michael+J.&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F364099.364331&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span>. The paper originating disjoint-set forests.</span> </li> <li id="cite_note-Hopcroft1973-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Hopcroft1973_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopcroftUllman1973" class="citation journal cs1"><a href="/wiki/John_Hopcroft" title="John Hopcroft">Hopcroft, J. E.</a>; <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Ullman, J. D.</a> (1973). "Set Merging Algorithms". <i>SIAM Journal on Computing</i>. <b>2</b> (4): <span class="nowrap">294–</span>303. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0202024">10.1137/0202024</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Set+Merging+Algorithms&rft.volume=2&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E294-%3C%2Fspan%3E303&rft.date=1973&rft_id=info%3Adoi%2F10.1137%2F0202024&rft.aulast=Hopcroft&rft.aufirst=J.+E.&rft.au=Ullman%2C+J.+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Tarjan1984-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-Tarjan1984_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Tarjan1984_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Tarjan1984_4-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTarjanvan_Leeuwen1984" class="citation journal cs1"><a href="/wiki/Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Tarjan, Robert E.</a>; <a href="/wiki/Jan_van_Leeuwen" title="Jan van Leeuwen">van Leeuwen, Jan</a> (1984). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62.2160">"Worst-case analysis of set union algorithms"</a>. <i>Journal of the ACM</i>. <b>31</b> (2): <span class="nowrap">245–</span>281. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62.2160">10.1145/62.2160</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5363073">5363073</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Worst-case+analysis+of+set+union+algorithms&rft.volume=31&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E245-%3C%2Fspan%3E281&rft.date=1984&rft_id=info%3Adoi%2F10.1145%2F62.2160&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A5363073%23id-name%3DS2CID&rft.aulast=Tarjan&rft.aufirst=Robert+E.&rft.au=van+Leeuwen%2C+Jan&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F62.2160&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Tarjan1979-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-Tarjan1979_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Tarjan1979_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTarjan1979" class="citation journal cs1"><a href="/wiki/Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Tarjan, Robert Endre</a> (1979). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2879%2990042-4">"A class of algorithms which require non-linear time to maintain disjoint sets"</a>. <i>Journal of Computer and System Sciences</i>. <b>18</b> (2): <span class="nowrap">110–</span>127. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2879%2990042-4">10.1016/0022-0000(79)90042-4</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=A+class+of+algorithms+which+require+non-linear+time+to+maintain+disjoint+sets&rft.volume=18&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E110-%3C%2Fspan%3E127&rft.date=1979&rft_id=info%3Adoi%2F10.1016%2F0022-0000%2879%2990042-4&rft.aulast=Tarjan&rft.aufirst=Robert+Endre&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252F0022-0000%252879%252990042-4&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Fredman1989-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-Fredman1989_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Fredman1989_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFredmanSaks1989" class="citation book cs1"><a href="/wiki/Michael_Fredman" title="Michael Fredman">Fredman, M.</a>; Saks, M. (May 1989). "The cell probe complexity of dynamic data structures". <i>Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89</i>. pp. <span class="nowrap">345–</span>354. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F73007.73040">10.1145/73007.73040</a></span>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0897913078" title="Special:BookSources/0897913078"><bdi>0897913078</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13470414">13470414</a>. <q>Theorem 5: Any CPROBE(log <i>n</i>) implementation of the set union problem requires Ω(<i>m</i> α(<i>m</i>, <i>n</i>)) time to execute <i>m</i> Find's and <i>n</i>−1 Union's, beginning with <i>n</i> singleton sets.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+cell+probe+complexity+of+dynamic+data+structures&rft.btitle=Proceedings+of+the+twenty-first+annual+ACM+symposium+on+Theory+of+computing+-+STOC+%2789&rft.pages=%3Cspan+class%3D%22nowrap%22%3E345-%3C%2Fspan%3E354&rft.date=1989-05&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A13470414%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F73007.73040&rft.isbn=0897913078&rft.aulast=Fredman&rft.aufirst=M.&rft.au=Saks%2C+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Galil1991-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-Galil1991_7-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGalilItaliano1991" class="citation journal cs1">Galil, Z.; Italiano, G. (1991). "Data structures and algorithms for disjoint set union problems". <i>ACM Computing Surveys</i>. <b>23</b> (3): <span class="nowrap">319–</span>344. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F116873.116878">10.1145/116873.116878</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207160759">207160759</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Computing+Surveys&rft.atitle=Data+structures+and+algorithms+for+disjoint+set+union+problems&rft.volume=23&rft.issue=3&rft.pages=%3Cspan+class%3D%22nowrap%22%3E319-%3C%2Fspan%3E344&rft.date=1991&rft_id=info%3Adoi%2F10.1145%2F116873.116878&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A207160759%23id-name%3DS2CID&rft.aulast=Galil&rft.aufirst=Z.&rft.au=Italiano%2C+G.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Anderson1994-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Anderson1994_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAndersonWoll1994" class="citation conference cs1">Anderson, Richard J.; Woll, Heather (1994). <i>Wait-free Parallel Algorithms for the Union-Find Problem</i>. 23rd ACM Symposium on Theory of Computing. pp. <span class="nowrap">370–</span>380.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=Wait-free+Parallel+Algorithms+for+the+Union-Find+Problem&rft.pages=%3Cspan+class%3D%22nowrap%22%3E370-%3C%2Fspan%3E380&rft.date=1994&rft.aulast=Anderson&rft.aufirst=Richard+J.&rft.au=Woll%2C+Heather&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Conchon2007-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-Conchon2007_9-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFConchonFilliâtre2007" class="citation conference cs1">Conchon, Sylvain; Filliâtre, Jean-Christophe (October 2007). "A Persistent Union-Find Data Structure". <a rel="nofollow" class="external text" href="https://www.lri.fr/~filliatr/puf/"><i>ACM SIGPLAN Workshop on ML</i></a>. Freiburg, Germany.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=A+Persistent+Union-Find+Data+Structure&rft.btitle=ACM+SIGPLAN+Workshop+on+ML&rft.place=Freiburg%2C+Germany&rft.date=2007-10&rft.aulast=Conchon&rft.aufirst=Sylvain&rft.au=Filli%C3%A2tre%2C+Jean-Christophe&rft_id=https%3A%2F%2Fwww.lri.fr%2F~filliatr%2Fpuf%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">Harold N. Gabow, Robert Endre Tarjan, "A linear-time algorithm for a special case of disjoint set union," Journal of Computer and System Sciences, Volume 30, Issue 2, 1985, pp. 209–221, ISSN 0022-0000, <a rel="nofollow" class="external free" href="https://doi.org/10.1016/0022-0000(85)90014-5">https://doi.org/10.1016/0022-0000(85)90014-5</a></span> </li> <li id="cite_note-Cormen2009-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-Cormen2009_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Cormen2009_11-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Cormen2009_11-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCormenLeisersonRivestStein2009" class="citation book cs1"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="/wiki/Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Rivest, Ronald L.</a>; <a href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2009). "Chapter 21: Data structures for Disjoint Sets". <a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a> (Third ed.). MIT Press. pp. <span class="nowrap">571–</span>572. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-262-03384-8" title="Special:BookSources/978-0-262-03384-8"><bdi>978-0-262-03384-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+21%3A+Data+structures+for+Disjoint+Sets&rft.btitle=Introduction+to+Algorithms&rft.pages=%3Cspan+class%3D%22nowrap%22%3E571-%3C%2Fspan%3E572&rft.edition=Third&rft.pub=MIT+Press&rft.date=2009&rft.isbn=978-0-262-03384-8&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><a href="/wiki/Raimund_Seidel" title="Raimund Seidel">Raimund Seidel</a>, Micha Sharir. "Top-down analysis of path compression", SIAM J. Comput. 34(3):515–525, 2005</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTarjan1975" class="citation journal cs1">Tarjan, Robert Endre (1975). <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=321884">"Efficiency of a Good But Not Linear Set Union Algorithm"</a>. <i>Journal of the ACM</i>. <b>22</b> (2): <span class="nowrap">215–</span>225. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321879.321884">10.1145/321879.321884</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F5942">1813/5942</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11105749">11105749</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Efficiency+of+a+Good+But+Not+Linear+Set+Union+Algorithm&rft.volume=22&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E215-%3C%2Fspan%3E225&rft.date=1975&rft_id=info%3Ahdl%2F1813%2F5942&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11105749%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F321879.321884&rft.aulast=Tarjan&rft.aufirst=Robert+Endre&rft_id=http%3A%2F%2Fportal.acm.org%2Fcitation.cfm%3Fid%3D321884&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopcroftUllman1973" class="citation journal cs1">Hopcroft, J. E.; Ullman, J. D. (1973). "Set Merging Algorithms". <i>SIAM Journal on Computing</i>. <b>2</b> (4): <span class="nowrap">294–</span>303. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0202024">10.1137/0202024</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Set+Merging+Algorithms&rft.volume=2&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E294-%3C%2Fspan%3E303&rft.date=1973&rft_id=info%3Adoi%2F10.1137%2F0202024&rft.aulast=Hopcroft&rft.aufirst=J.+E.&rft.au=Ullman%2C+J.+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><a href="/wiki/Robert_E._Tarjan" class="mw-redirect" title="Robert E. Tarjan">Robert E. Tarjan</a> and <a href="/wiki/Jan_van_Leeuwen" title="Jan van Leeuwen">Jan van Leeuwen</a>. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBlum1985" class="citation journal cs1">Blum, Norbert (1985). "On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem". <i>2nd Symp. On Theoretical Aspects of Computer Science</i>: <span class="nowrap">32–</span>38.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=2nd+Symp.+On+Theoretical+Aspects+of+Computer+Science&rft.atitle=On+the+Single-Operation+Worst-Case+Time+Complexity+of+the+Disjoint+Set+Union+Problem&rft.pages=%3Cspan+class%3D%22nowrap%22%3E32-%3C%2Fspan%3E38&rft.date=1985&rft.aulast=Blum&rft.aufirst=Norbert&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlstrupBen-AmramRauhe1999" class="citation book cs1">Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Worst-case and amortised optimality in union-find (Extended abstract)". <i>Proceedings of the thirty-first annual ACM symposium on Theory of Computing</i>. pp. <span class="nowrap">499–</span>506. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F301250.301383">10.1145/301250.301383</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/1581130678" title="Special:BookSources/1581130678"><bdi>1581130678</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:100111">100111</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Worst-case+and+amortised+optimality+in+union-find+%28Extended+abstract%29&rft.btitle=Proceedings+of+the+thirty-first+annual+ACM+symposium+on+Theory+of+Computing&rft.pages=%3Cspan+class%3D%22nowrap%22%3E499-%3C%2Fspan%3E506&rft.date=1999&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A100111%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F301250.301383&rft.isbn=1581130678&rft.aulast=Alstrup&rft.aufirst=Stephen&rft.au=Ben-Amram%2C+Amir+M.&rft.au=Rauhe%2C+Theis&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlstrupThorupGørtzRauhe2014" class="citation journal cs1">Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri (2014). "Union-Find with Constant Time Deletions". <i>ACM Transactions on Algorithms</i>. <b>11</b> (1): 6:1–6:28. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2636922">10.1145/2636922</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12767012">12767012</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Algorithms&rft.atitle=Union-Find+with+Constant+Time+Deletions&rft.volume=11&rft.issue=1&rft.pages=6%3A1-6%3A28&rft.date=2014&rft_id=info%3Adoi%2F10.1145%2F2636922&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A12767012%23id-name%3DS2CID&rft.aulast=Alstrup&rft.aufirst=Stephen&rft.au=Thorup%2C+Mikkel&rft.au=G%C3%B8rtz%2C+Inge+Li&rft.au=Rauhe%2C+Theis&rft.au=Zwick%2C+Uri&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBen-AmramYoffe2011" class="citation journal cs1">Ben-Amram, Amir M.; Yoffe, Simon (2011). "A simple and efficient Union-Find-Delete algorithm". <i>Theoretical Computer Science</i>. <b>412</b> (<span class="nowrap">4–</span>5): <span class="nowrap">487–</span>492. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2010.11.005">10.1016/j.tcs.2010.11.005</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=A+simple+and+efficient+Union-Find-Delete+algorithm&rft.volume=412&rft.issue=%3Cspan+class%3D%22nowrap%22%3E4%E2%80%93%3C%2Fspan%3E5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E487-%3C%2Fspan%3E492&rft.date=2011&rft_id=info%3Adoi%2F10.1016%2Fj.tcs.2010.11.005&rft.aulast=Ben-Amram&rft.aufirst=Amir+M.&rft.au=Yoffe%2C+Simon&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> <li id="cite_note-Knight1989-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-Knight1989_20-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKnight1989" class="citation journal cs1">Knight, Kevin (1989). <a rel="nofollow" class="external text" href="http://www.isi.edu/natural-language/people/unification-knight.pdf">"Unification: A multidisciplinary survey"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Computing Surveys</i>. <b>21</b>: <span class="nowrap">93–</span>124. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62029.62030">10.1145/62029.62030</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14619034">14619034</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Computing+Surveys&rft.atitle=Unification%3A+A+multidisciplinary+survey&rft.volume=21&rft.pages=%3Cspan+class%3D%22nowrap%22%3E93-%3C%2Fspan%3E124&rft.date=1989&rft_id=info%3Adoi%2F10.1145%2F62029.62030&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A14619034%23id-name%3DS2CID&rft.aulast=Knight&rft.aufirst=Kevin&rft_id=http%3A%2F%2Fwww.isi.edu%2Fnatural-language%2Fpeople%2Funification-knight.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADisjoint-set+data+structure" class="Z3988"></span></span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Disjoint-set_data_structure&action=edit&section=17" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://www.boost.org/doc/libs/1_31_0/libs/disjoint_sets/disjoint_sets.html">C++ implementation</a>, part of the <a href="/wiki/Boost_C%2B%2B_libraries" class="mw-redirect" title="Boost C++ libraries">Boost C++ libraries</a></li> <li><a rel="nofollow" class="external text" href="https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/util/UnionFind.java">Java implementation</a>, part of <a rel="nofollow" class="external text" href="https://jgrapht.org/">JGraphT library</a></li> <li><a rel="nofollow" class="external text" href="https://the-algorithms.com/algorithm/union-find">Javascript implementation</a></li> <li><a rel="nofollow" class="external text" href="http://code.activestate.com/recipes/215912-union-find-data-structure/">Python implementation</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures216" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures216" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</a> <ul><li><a href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li> <li><a class="mw-selflink selflink">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/B-tree" title="B-tree">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a href="/wiki/Trie" title="Trie">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Disjoint-set_data_structure&oldid=1267325423">https://en.wikipedia.org/w/index.php?title=Disjoint-set_data_structure&oldid=1267325423</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Search_algorithms" title="Category:Search algorithms">Search algorithms</a></li><li><a href="/wiki/Category:Amortized_data_structures" title="Category:Amortized data structures">Amortized data structures</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_with_example_pseudocode" title="Category:Articles with example pseudocode">Articles with example pseudocode</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 4 January 2025, at 16:42<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Disjoint-set_data_structure&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Disjoint-set data structure</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>21 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-d8647bfd6-7hh8m","wgBackendResponseTime":135,"wgPageParseReport":{"limitreport":{"cputime":"0.737","walltime":"0.980","ppvisitednodes":{"value":4052,"limit":1000000},"postexpandincludesize":{"value":74423,"limit":2097152},"templateargumentsize":{"value":7561,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":81902,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 699.970 1 -total"," 28.53% 199.698 1 Template:Reflist"," 23.00% 161.012 2 Template:Annotated_link"," 20.49% 143.429 12 Template:Cite_journal"," 14.59% 102.117 1 Template:Data_structures"," 13.71% 95.975 1 Template:Navbox"," 12.37% 86.600 1 Template:Short_description"," 11.39% 79.699 1 Template:Infobox_data_structure"," 10.45% 73.135 1 Template:Infobox"," 8.74% 61.211 2 Template:Pagetype"]},"scribunto":{"limitreport-timeusage":{"value":"0.444","limit":"10.000"},"limitreport-memusage":{"value":25571481,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-84749c7844-dwk82","timestamp":"20250207184316","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Disjoint-set data structure","url":"https:\/\/en.wikipedia.org\/wiki\/Disjoint-set_data_structure","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1259393","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1259393","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-10-03T22:21:30Z","dateModified":"2025-01-04T16:42:27Z","headline":"data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets"}</script> </body> </html>