You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{"payload":{"allShortcutsEnabled":false,"path":"Union-Find","repo":{"id":169615200,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"jerrytdev","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-02-07T17:48:35.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/3459767?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1615655657.482121","canEdit":false,"refType":"branch","currentOid":"ff780b6ff7d25b2aa79cbeef5ac72de6ce76b77e"},"tree":{"items":[{"name":"Images","path":"Union-Find/Images","contentType":"directory"},{"name":"UnionFind.playground","path":"Union-Find/UnionFind.playground","contentType":"directory"},{"name":"README.markdown","path":"Union-Find/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eUnion-Find\u003c/h1\u003e\u003ca id=\"user-content-union-find\" class=\"anchor\" aria-label=\"Permalink: Union-Find\" href=\"#union-find\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eUnion-Find is a data structure that can keep track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It is also known as disjoint-set data structure.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWhat do we mean by this? For example, the Union-Find data structure could be keeping track of the following sets:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ a, b, f, k ]\n[ e ]\n[ g, d, c ]\n[ i, j ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ a, b, f, k ]\n[ e ]\n[ g, d, c ]\n[ i, j ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThese sets are \u003cstrong\u003edisjoint\u003c/strong\u003e because they have no members in common.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eUnion-Find supports three basic operations:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eFind(A)\u003c/strong\u003e: Determine which subset an element \u003cstrong\u003eA\u003c/strong\u003e is in. For example, \u003ccode\u003efind(d)\u003c/code\u003e would return the subset \u003ccode\u003e[ g, d, c ]\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eUnion(A, B)\u003c/strong\u003e: Join two subsets that contain \u003cstrong\u003eA\u003c/strong\u003e and \u003cstrong\u003eB\u003c/strong\u003e into a single subset. For example, \u003ccode\u003eunion(d, j)\u003c/code\u003e would combine \u003ccode\u003e[ g, d, c ]\u003c/code\u003e and \u003ccode\u003e[ i, j ]\u003c/code\u003e into the larger set \u003ccode\u003e[ g, d, c, i, j ]\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eAddSet(A)\u003c/strong\u003e: Add a new subset containing just that element \u003cstrong\u003eA\u003c/strong\u003e. For example, \u003ccode\u003eaddSet(h)\u003c/code\u003e would add a new set \u003ccode\u003e[ h ]\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eThe most common application of this data structure is keeping track of the connected components of an undirected \u003ca href=\"/jerrytdev/swift-algorithm-club/blob/master/Graph\"\u003egraph\u003c/a\u003e. It is also used for implementing an efficient version of Kruskal's algorithm to find the minimum spanning tree of a graph.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eImplementation\u003c/h2\u003e\u003ca id=\"user-content-implementation\" class=\"anchor\" aria-label=\"Permalink: Implementation\" href=\"#implementation\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eUnion-Find can be implemented in many ways but we'll look at an efficient and easy to understand implementation: Weighted Quick Union.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003ePS: Multiple implementations of Union-Find has been included in playground.\u003c/strong\u003e\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public struct UnionFind\u0026lt;T: Hashable\u0026gt; {\n private var index = [T: Int]()\n private var parent = [Int]()\n private var size = [Int]()\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eUnionFind\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eHashable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eindex\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e Int\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eparent\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eInt\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003esize\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eInt\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eOur Union-Find data structure is actually a forest where each subset is represented by a \u003ca href=\"/jerrytdev/swift-algorithm-club/blob/master/Tree\"\u003etree\u003c/a\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor our purposes we only need to keep track of the parent of each tree node, not the node's children. To do this we use the array \u003ccode\u003eparent\u003c/code\u003e so that \u003ccode\u003eparent[i]\u003c/code\u003e is the index of node \u003ccode\u003ei\u003c/code\u003e's parent.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eExample: If \u003ccode\u003eparent\u003c/code\u003e looks like this,\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"parent [ 1, 1, 1, 0, 2, 0, 6, 6, 6 ]\n i 0 1 2 3 4 5 6 7 8\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eparent [ 1, 1, 1, 0, 2, 0, 6, 6, 6 ]\n i 0 1 2 3 4 5 6 7 8\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003ethen the tree structure looks like:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 6\n / \\ / \\\n 0 2 7 8\n / \\ /\n3 5 4\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 6\n / \\ / \\\n 0 2 7 8\n / \\ /\n3 5 4\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThere are two trees in this forest, each of which corresponds to one set of elements. (Note: due to the limitations of ASCII art the trees are shown here as binary trees but that is not necessarily the case.)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe give each subset a unique number to identify it. That number is the index of the root node of that subset's tree. In the example, node \u003ccode\u003e1\u003c/code\u003e is the root of the first tree and \u003ccode\u003e6\u003c/code\u003e is the root of the second tree.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSo in this example we have two subsets, the first with the label \u003ccode\u003e1\u003c/code\u003e and the second with the label \u003ccode\u003e6\u003c/code\u003e. The \u003cstrong\u003eFind\u003c/strong\u003e operation actually returns the set's label, not its contents.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNote that the \u003ccode\u003eparent[]\u003c/code\u003e of a root node points to itself. So \u003ccode\u003eparent[1] = 1\u003c/code\u003e and \u003ccode\u003eparent[6] = 6\u003c/code\u003e. That's how we can tell something is a root node.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eAdd set\u003c/h2\u003e\u003ca id=\"user-content-add-set\" class=\"anchor\" aria-label=\"Permalink: Add set\" href=\"#add-set\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's look at the implementation of these basic operations, starting with adding a new set.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public mutating func addSetWith(_ element: T) {\n index[element] = parent.count // 1\n parent.append(parent.count) // 2\n size.append(1) // 3\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e addSetWith\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ element\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eindex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eelement\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e parent\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount // 1\n parent\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eparent\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 2\n size\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 3\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWhen you add a new element, this actually adds a new subset containing just that element.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eWe save the index of the new element in the \u003ccode\u003eindex\u003c/code\u003e dictionary. That lets us look up the element quickly later on.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThen we add that index to the \u003ccode\u003eparent\u003c/code\u003e array to build a new tree for this set. Here, \u003ccode\u003eparent[i]\u003c/code\u003e is pointing to itself because the tree that represents the new set contains only one node, which of course is the root of that tree.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003esize[i]\u003c/code\u003e is the count of nodes in the tree whose root is at index \u003ccode\u003ei\u003c/code\u003e. For the new set this is 1 because it only contains the one element. We'll be using the \u003ccode\u003esize\u003c/code\u003e array in the Union operation.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eFind\u003c/h2\u003e\u003ca id=\"user-content-find\" class=\"anchor\" aria-label=\"Permalink: Find\" href=\"#find\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eOften we want to determine whether we already have a set that contains a given element. That's what the \u003cstrong\u003eFind\u003c/strong\u003e operation does. In our \u003ccode\u003eUnionFind\u003c/code\u003e data structure it is called \u003ccode\u003esetOf()\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public mutating func setOf(_ element: T) -\u0026gt; Int? {\n if let indexOfElement = index[element] {\n return setByIndex(indexOfElement)\n } else {\n return nil\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e setOf\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ element\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e indexOfElement \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eindex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eelement\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetByIndex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eindexOfElement\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis looks up the element's index in the \u003ccode\u003eindex\u003c/code\u003e dictionary and then uses a helper method to find the set that this element belongs to:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"private mutating func setByIndex(_ index: Int) -\u0026gt; Int {\n if parent[index] == index { // 1\n return index\n } else {\n parent[index] = setByIndex(parent[index]) // 2\n return parent[index] // 3\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e setByIndex\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ index\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e index \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 1\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e index\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetByIndex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 2\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e // 3\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eBecause we're dealing with a tree structure, this is a recursive method.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eRecall that each set is represented by a tree and that the index of the root node serves as the number that identifies the set. We're going to find the root node of the tree that the element we're searching for belongs to, and return its index.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eFirst, we check if the given index represents a root node (i.e. a node whose \u003ccode\u003eparent\u003c/code\u003e points back to the node itself). If so, we're done.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eOtherwise we recursively call this method on the parent of the current node. And then we do a \u003cstrong\u003every important thing\u003c/strong\u003e: we overwrite the parent of the current node with the index of root node, in effect reconnecting the node directly to the root of the tree. The next time we call this method, it will execute faster because the path to the root of the tree is now much shorter. Without that optimization, this method's complexity is \u003cstrong\u003eO(n)\u003c/strong\u003e but now in combination with the size optimization (covered in the Union section) it is almost \u003cstrong\u003eO(1)\u003c/strong\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eWe return the index of the root node as the result.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eHere's illustration of what I mean. Let's say the tree looks like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/jerrytdev/swift-algorithm-club/blob/master/Union-Find/Images/BeforeFind.png\"\u003e\u003cimg src=\"/jerrytdev/swift-algorithm-club/raw/master/Union-Find/Images/BeforeFind.png\" alt=\"BeforeFind\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWe call \u003ccode\u003esetOf(4)\u003c/code\u003e. To find the root node we have to first go to node \u003ccode\u003e2\u003c/code\u003e and then to node \u003ccode\u003e7\u003c/code\u003e. (The indices of the elements are marked in red.)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eDuring the call to \u003ccode\u003esetOf(4)\u003c/code\u003e, the tree is reorganized to look like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/jerrytdev/swift-algorithm-club/blob/master/Union-Find/Images/AfterFind.png\"\u003e\u003cimg src=\"/jerrytdev/swift-algorithm-club/raw/master/Union-Find/Images/AfterFind.png\" alt=\"AfterFind\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNow if we need to call \u003ccode\u003esetOf(4)\u003c/code\u003e again, we no longer have to go through node \u003ccode\u003e2\u003c/code\u003e to get to the root. So as you use the Union-Find data structure, it optimizes itself. Pretty cool!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThere is also a helper method to check that two elements are in the same set:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public mutating func inSameSet(_ firstElement: T, and secondElement: T) -\u0026gt; Bool {\n if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) {\n return firstSet == secondSet\n } else {\n return false\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e inSameSet\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ firstElement\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e and secondElement\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBool\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e firstSet \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efirstElement\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e secondSet \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003esecondElement\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e firstSet \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e secondSet\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eSince this calls \u003ccode\u003esetOf()\u003c/code\u003e it also optimizes the tree.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eUnion (Weighted)\u003c/h2\u003e\u003ca id=\"user-content-union-weighted\" class=\"anchor\" aria-label=\"Permalink: Union (Weighted)\" href=\"#union-weighted\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe final operation is \u003cstrong\u003eUnion\u003c/strong\u003e, which combines two sets into one larger set.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\" public mutating func unionSetsContaining(_ firstElement: T, and secondElement: T) {\n if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { // 1\n if firstSet != secondSet { // 2\n if size[firstSet] \u0026lt; size[secondSet] { // 3\n parent[firstSet] = secondSet // 4\n size[secondSet] += size[firstSet] // 5\n } else {\n parent[secondSet] = firstSet\n size[firstSet] += size[secondSet]\n }\n }\n }\n }\"\u003e\u003cpre\u003e \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e unionSetsContaining\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ firstElement\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e and secondElement\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e firstSet \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efirstElement\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e secondSet \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003esecondElement\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 1\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e firstSet \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e secondSet \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 2\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esize\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003efirstSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esize\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003esecondSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 3\n \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003efirstSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e secondSet // 4\n \u003cspan class=\"pl-en\"\u003esize\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003esecondSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esize\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003efirstSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e // 5\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003esecondSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e firstSet\n \u003cspan class=\"pl-en\"\u003esize\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003efirstSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esize\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003esecondSet\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eHere is how it works:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eWe find the sets that each element belongs to. Remember that this gives us two integers: t
85C1
he indices of the root nodes in the \u003ccode\u003eparent\u003c/code\u003e array.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eCheck that the sets are not equal because if they are it makes no sense to union them.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThis is where the size optimization comes in (Weighting). We want to keep the trees as shallow as possible so we always attach the smaller tree to the root of the larger tree. To determine which is the smaller tree we compare trees by their sizes.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eHere we attach the smaller tree to the root of the larger tree.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eUpdate the size of larger tree because it just had a bunch of nodes added to it.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eAn illustration may help to better understand this. Let's say we have these two sets, each with its own tree:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/jerrytdev/swift-algorithm-club/blob/master/Union-Find/Images/BeforeUnion.png\"\u003e\u003cimg src=\"/jerrytdev/swift-algorithm-club/raw/master/Union-Find/Images/BeforeUnion.png\" alt=\"BeforeUnion\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNow we call \u003ccode\u003eunionSetsContaining(4, and: 3)\u003c/code\u003e. The smaller tree is attached to the larger one:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/jerrytdev/swift-algorithm-club/blob/master/Union-Find/Images/AfterUnion.png\"\u003e\u003cimg src=\"/jerrytdev/swift-algorithm-club/raw/master/Union-Find/Images/AfterUnion.png\" alt=\"AfterUnion\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNote that, because we call \u003ccode\u003esetOf()\u003c/code\u003e at the start of the method, the larger tree was also optimized in the process -- node \u003ccode\u003e3\u003c/code\u003e now hangs directly off the root.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eUnion with optimizations also takes almost \u003cstrong\u003eO(1)\u003c/strong\u003e time.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003ePath Compression\u003c/h2\u003e\u003ca id=\"user-content-path-compression\" class=\"anchor\" aria-label=\"Permalink: Path Compression\" href=\"#path-compression\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"private mutating func setByIndex(_ index: Int) -\u0026gt; Int {\n if index != parent[index] {\n // Updating parent index while looking up the index of parent.\n parent[index] = setByIndex(parent[index])\n }\n return parent[index]\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e setByIndex\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ index\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e index \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n // Updating parent index while looking up the index of parent.\n \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esetByIndex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eparent\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eindex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003ePath Compression helps keep trees very flat, thus find operation could take \u003cstrong\u003eALMOST\u003c/strong\u003e in \u003cstrong\u003eO(1)\u003c/strong\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eComplexity Summary\u003c/h2\u003e\u003ca id=\"user-content-complexity-summary\" class=\"anchor\" aria-label=\"Permalink: Complexity Summary\" href=\"#complexity-summary\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch5 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eTo process N objects\u003c/h5\u003e\u003ca id=\"user-content-to-process-n-objects\" class=\"anchor\" aria-label=\"Permalink: To process N objects\" href=\"#to-process-n-objects\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cmarkdown-accessiblity-table\u003e\u003ctable\u003e\n\u003cthead\u003e\n\u003ctr\u003e\n\u003cth\u003eData Structure\u003c/th\u003e\n\u003cth\u003eUnion\u003c/th\u003e\n\u003cth\u003eFind\u003c/th\u003e\n\u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n\u003ctr\u003e\n\u003ctd\u003eQuick Find\u003c/td\u003e\n\u003ctd\u003eN\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003eQuick Union\u003c/td\u003e\n\u003ctd\u003eTree height\u003c/td\u003e\n\u003ctd\u003eTree height\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003eWeighted Quick Union\u003c/td\u003e\n\u003ctd\u003elgN\u003c/td\u003e\n\u003ctd\u003elgN\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003eWeighted Quick Union + Path Compression\u003c/td\u003e\n\u003ctd\u003every close, but not O(1)\u003c/td\u003e\n\u003ctd\u003every close, but not O(1)\u003c/td\u003e\n\u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\u003c/markdown-accessiblity-table\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch5 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eTo process M union commands on N objects\u003c/h5\u003e\u003ca id=\"user-content-to-process-m-union-commands-on-n-objects\" class=\"anchor\" aria-label=\"Permalink: To process M union commands on N objects\" href=\"#to-process-m-union-commands-on-n-objects\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cmarkdown-accessiblity-table\u003e\u003ctable\u003e\n\u003cthead\u003e\n\u003ctr\u003e\n\u003cth\u003eAlgorithm\u003c/th\u003e\n\u003cth\u003eWorst-case time\u003c/th\u003e\n\u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n\u003ctr\u003e\n\u003ctd\u003eQuick Find\u003c/td\u003e\n\u003ctd\u003eM N\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003eQuick Union\u003c/td\u003e\n\u003ctd\u003eM N\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003eWeighted Quick Union\u003c/td\u003e\n\u003ctd\u003eN + M lgN\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003eWeighted Quick Union + Path Compression\u003c/td\u003e\n\u003ctd\u003e(M + N) lgN\u003c/td\u003e\n\u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\u003c/markdown-accessiblity-table\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSee also\u003c/h2\u003e\u003ca id=\"user-content-see-also\" class=\"anchor\" aria-label=\"Permalink: See also\" href=\"#see-also\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eSee the playground for more examples of how to use this handy data structure.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Disjoint-set_data_structure\" rel=\"nofollow\"\u003eUnion-Find at Wikipedia\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by \u003ca href=\"https://github.com/goingreen\"\u003eArtur Antonov\u003c/a\u003e\u003c/em\u003e, \u003cem\u003emodified by \u003ca href=\"https://github.com/antonio081014\"\u003eYi Ding\u003c/a\u003e.\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Union-Find","anchor":"union-find","htmlText":"Union-Find"},{"level":2,"text":"Implementation","anchor":"implementation","htmlText":"Implementation"},{"level":2,"text":"Add set","anchor":"add-set","htmlText":"Add set"},{"level":2,"text":"Find","anchor":"find","htmlText":"Find"},{"level":2,"text":"Union (Weighted)","anchor":"union-weighted","htmlText":"Union (Weighted)"},{"level":2,"text":"Path Compression","anchor":"path-compression","htmlText":"Path Compression"},{"level":2,"text":"Complexity Summary","anchor":"complexity-summary","htmlText":"Complexity Summary"},{"level":5,"text":"To process N objects","anchor":"to-process-n-objects","htmlText":"To process N objects"},{"level":5,"text":"To process M union commands on N objects","anchor":"to-process-m-union-commands-on-n-objects","htmlText":"To process M union commands on N objects"},{"level":2,"text":"See also","anchor":"see-also","htmlText":"See also"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fjerrytdev%2Fswift-algorithm-club%2Ftree%2Fmaster%2FUnion-Find"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":"swift-algorithm-club.xcworkspace","path":"swift-algorithm-club.xcworkspace","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":116}},"fileTreeProcessingTime":4.548084,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/jerrytdev/swift-algorithm-club/branches":{"post":"hZHyphKCmvaci3PHInqRWQUMsZfzJtuULQzVV517txgm4Mv7OAMr5BxpdKmPoAwImsjCJLhPEelWI8UogkwSew"},"/jerrytdev/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"wwXhifvxoNbZTgg-VcjfACJsVg7DaUZuHZqxvCzYX1g4fydTxe8tiEA5W1YAffwMhJwdgzHZky-UO2hYTxewXw"},"/jerrytdev/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"R14-h1N-87FWF3jrYVIjzPxcYdnPcRH0ivoU5Bai8ti8JPhdbWB-789gK4M05wDAWqwqVD3BxLUDW80AdW0d3w"}}},"title":"swift-algorithm-club/Union-Find at master · jerrytdev/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}