[Union Find Tutorial] Number of Provinces
Topic :  Union Find\nA data structure that stores non overlapping or disjoint subset of elements is called Disjoint Set or Union Find data structure. In the Uni
**Topic** :  Union Find\nA data structure that stores non overlapping or disjoint subset of elements is called **Disjoint Set** or **Union Find** data structure. In the Union-Find data structure, each connected component (disjoint subset) is represented as a forest (or collection) of trees where each tree is rooted and nodes point to their parent. **Note that in this structure, the root node of each tree points to itself**. The elements of each subset are the nodes within these trees. The Union-Find data structure supports following operations:\n* Merging disjoint sets to a single disjoint set using **Union** operation.\n* Finding representative of a disjoint set using **Find** operation.\n* Check if two sets are disjoint or not. \n\n<br/>\n\n**Implementation**:\n\nLet\'s use Java as the example code for the Union-Find template:\n```\nclass UF {\n    int[] p;\n    int[] height;\n\n    UF(int n) {\n        p = new int[n];\n        height = new int[n];\n        for (int i = 0; i < n; i++) {\n            p[i] = i;\n            height[i] = 1;\n        }\n    }\n\n    int find(int u) {\n        if (p[u] == u) return u;\n        return find(p[u]);\n    }\n\n    void merge(int root1, int root2) {\n        if (root1 == root2) return;\n        if (height[root1] < height[root2]) {\n            int temp = root1;\n            root1 = root2;\n            root2 = temp;\n        }\n        p[root2] = root1;\n        height[root1] = Math.max(height[root1], 1 + height[root2]);\n    }\n}\n```\n\n<br/><br/>\n\n* Initially, in the Union-Find data structure, each node is its own root, forming a singleton tree (disjoint subset) where the node\'s parent points to itself.\n\t![image](https://assets.leetcode.com/users/images/62a0785e-ccf6-46ba-a7a7-fed3e0e33146_1720248758.069805.png)\n\tThis initialization is done in the constructor of the UF data structure. We use `p[i]` to denote the parent of node i and `height[i]` to denote the height of the subtree with root node `i`. `p[i] = i` denotes that initially, each node is its own root.\n\t```\n\tUF(int n) {\n        p = new int[n];\n        height = new int[n];\n        for (int i = 0; i < n; i++) {\n            p[i] = i;\n            height[i] = 1;\n        }\n    }\n\t```\n<br/><br/>\n\n* With the **find** operation, we traverse upwards to find the root of the current tree. This process stops when `p[u] = u`, indicating that `u` is the root node pointing to itself.\n![image](https://assets.leetcode.com/users/images/3876a3e1-e0e4-4f79-9ffe-b48136fc771a_1720249118.2456112.png)\n\tThis is done via the `find` method:\n\t```\n\tint find(int u) {\n        if (p[u] == u) return u;\n        return find(p[u]);\n    }\n\t```\n\t\n<br/><br/>\n* With the **Union** or **Merge** operation, we combine two trees (disjoint sets) into a single tree (disjoint set). In order to merge two trees, we simply set the root of one tree to point to the root of the other tree. **Note that before merging two roots, we must ensure they are not already in the same connected component**.\n\n\tTo optimize performance, we always merge the tree with smaller height to point to the root of the tree with greater height. \n\n\tThis is done via the `merge` method:\n\t```\n\tvoid merge(int root1, int root2) {\n        if (root1 == root2) return;\n        if (height[root1] < height[root2]) {\n            int temp = root1;\n            root1 = root2;\n            root2 = temp;\n        }\n        p[root2] = root1;\n        height[root1] = Math.max(height[root1], 1 + height[root2]);\n    }\n\t```\n<br/><br/>\t\n* Time Complexity :\n\t* **Find** : `O(h)`, where `h` denotes the height of the tree. Given that we merge trees by always attaching the smaller tree under the root of the larger tree, the maximum height of any tree is `O(logn)` at most.\n\t* **Union** : `O(1)`.\n\t* **Constructor** : `O(n)`.\n* Space Complexity : `O(n)`\n___\n\n## Solution\nThe solution is straightforward: we use Union-Find to merge all connected nodes and then count the number of disjoint components at the end. \n\nAll nodes that are connected to each other can reach each other, so we place them within the same disjoint set to signify their mutual accessibility.\n\n<br/>\n\n```c++ []\nclass UF {\n    public:\n        vector<int> p; //parent\n        vector<int> height; //size\n        UF(int n) {\n            for(int i = 0; i < n; i++) {\n                p.push_back(i);\n                height.push_back(1);\n            }\n        }\n\n        int find(int u) {\n            return p[u] == u ? u : find(p[u]);\n        }\n\n        void merge(int root1, int root2) {\n            if(root1 == root2) {\n                return;\n            }\n            if(height[root1] < height[root2]) {\n                swap(root1, root2);\n            }\n            p[root1] = root2;\n            height[root2] = max(height[root2], 1 + height[root1]);\n        }\n};\n\nclass Solution {\npublic:\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        int n = isConnected.size();\n        UF uf(n);\n        for(int i = 0; i < n; i++) {\n            for(int j = i + 1; j < n; j++) {\n                if(isConnected[i][j] == 1) {\n                    int root1 = uf.find(i);\n                    int root2 = uf.find(j);\n                    uf.merge(root1, root2);\n                }\n            }\n        }\n        \n        set<int> components;\n        for(int i = 0; i < n; i++) {\n            components.insert(uf.find(i));\n        }\n        return components.size();\n    }\n};\n```\n```java []\nclass UF {\n    int[] p;\n    int[] height;\n\n    UF(int n) {\n        p = new int[n];\n        height = new int[n];\n        for (int i = 0; i < n; i++) {\n            p[i] = i;\n            height[i] = 1;\n        }\n    }\n\n    int find(int u) {\n        if (p[u] == u) return u;\n        return find(p[u]);\n    }\n\n    void merge(int root1, int root2) {\n        if (root1 == root2) return;\n        if (height[root1] < height[root2]) {\n            int temp = root1;\n            root1 = root2;\n            root2 = temp;\n        }\n        p[root2] = root1;\n        height[root1] = Math.max(height[root1], 1 + height[root2]);\n    }\n}\n\nclass Solution {\n    public int findCircleNum(int[][] isConnected) {\n        int n = isConnected.length;\n        UF uf = new UF(n);\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (isConnected[i][j] == 1) {\n                    int root1 = uf.find(i);\n                    int root2 = uf.find(j);\n                    uf.merge(root1, root2);\n                }\n            }\n        }\n        \n        Set<Integer> components = new HashSet<>();\n        for (int i = 0; i < n; i++) {\n            components.add(uf.find(i));\n        }\n        \n        return components.size();\n    }\n}\n```\n```python []\nclass UF:\n    def __init__(self, n):\n        self.p = list(range(n))\n        self.height = [1] * n\n\n    def find(self, u):\n        if self.p[u] == u:\n            return u\n        return self.find(self.p[u])\n\n    def merge(self, root1, root2):\n        if root1 == root2:\n            return\n        if self.height[root1] < self.height[root2]:\n            root1, root2 = root2, root1\n        self.p[root2] = root1\n        self.height[root1] = max(self.height[root1], 1 + self.height[root2])\n\nclass Solution:\n    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n        n = len(isConnected)\n        uf = UF(n)\n        for i in range(n):\n            for j in range(i + 1, n):\n                if isConnected[i][j] == 1:\n                    root1 = uf.find(i)\n                    root2 = uf.find(j)\n                    uf.merge(root1, root2)\n        \n        components = set()\n        for i in range(n):\n            components.add(uf.find(i))\n        \n        return len(components) \n```\n```Go []\ntype UF struct {\n\tp      []int\n\theight []int\n}\n\nfunc NewUF(n int) *UF {\n\tuf := UF{}\n\tuf.p = make([]int, n)\n\tuf.height = make([]int, n)\n\tfor i := 0; i < n; i++ {\n\t\tuf.p[i] = i\n\t\tuf.height[i] = 1\n\t}\n\treturn &uf\n}\n\nfunc (uf *UF) find(u int) int {\n\tif uf.p[u] == u {\n\t\treturn u\n\t}\n\treturn uf.find(uf.p[u])\n}\n\nfunc (uf *UF) merge(root1, root2 int) {\n\tif root1 == root2 {\n\t\treturn\n\t}\n\tif uf.height[root1] < uf.height[root2] {\n\t\troot1, root2 = root2, root1\n\t}\n\tuf.p[root2] = root1\n\tuf.height[root1] = max(uf.height[root1], 1+uf.height[root2])\n}\n\nfunc findCircleNum(isConnected [][]int) int {\n    n := len(isConnected)\n\tuf := NewUF(n)\n\tfor i := 0; i < n; i++ {\n\t\tfor j := i + 1; j < n; j++ {\n\t\t\tif isConnected[i][j] == 1 {\n\t\t\t\troot1 := uf.find(i)\n\t\t\t\troot2 := uf.find(j)\n\t\t\t\tuf.merge(root1, root2)\n\t\t\t}\n\t\t}\n\t}\n\t\n\tcomponents := make(map[int]bool)\n\tfor i := 0; i < n; i++ {\n\t\tcomponents[uf.find(i)] = true\n\t}\n\t\n\treturn len(components)\n}\n```\n```PHP []\nclass UF {\n    private $p;\n    private $height;\n\n    function __construct($n) {\n        $this->p = range(0, $n - 1);\n        $this->height = array_fill(0, $n, 1);\n    }\n\n    function find($u) {\n        if ($this->p[$u] == $u) return $u;\n        return $this->find($this->p[$u]);\n    }\n\n    function merge($root1, $root2) {\n        if ($root1 == $root2) return;\n        if ($this->height[$root1] < $this->height[$root2]) {\n            list($root1, $root2) = array($root2, $root1);\n        }\n        $this->p[$root2] = $root1;\n        $this->height[$root1] = max($this->height[$root1], 1 + $this->height[$root2]);\n    }\n}\n\nclass Solution {\n\n    /**\n     * @param Integer[][] $isConnected\n     * @return Integer\n     */\n    function findCircleNum($isConnected) {\n        $n = count($isConnected);\n        $uf = new UF($n);\n        for ($i = 0; $i < $n; $i++) {\n            for ($j = $i + 1; $j < $n; $j++) {\n                if ($isConnected[$i][$j] == 1) {\n                    $root1 = $uf->find($i);\n                    $root2 = $uf->find($j);\n                    $uf->merge($root1, $root2);\n                }\n            }\n        }\n        \n        $components = [];\n        for ($i = 0; $i < $n; $i++) {\n            $components[$uf->find($i)] = true;\n        }\n        \n        return count($components);\n    }\n}\n```\n```javascript []\n/**\n * @param {number[][]} isConnected\n * @return {number}\n */\n\nclass UF {\n    constructor(n) {\n        this.p = [...Array(n).keys()];\n        this.height = Array(n).fill(1);\n    }\n\n    find(u) {\n        if (this.p[u] === u) return u;\n        return this.find(this.p[u]);\n    }\n\n    merge(root1, root2) {\n        if (root1 === root2) return;\n        if (this.height[root1] < this.height[root2]) {\n            [root1, root2] = [root2, root1];\n        }\n        this.p[root2] = root1;\n        this.height[root1] = Math.max(this.height[root1], 1 + this.height[root2]);\n    }\n}\n\nvar findCircleNum = function(isConnected) {\n    const n = isConnected.length;\n    const uf = new UF(n);\n    for (let i = 0; i < n; i++) {\n        for (let j = i + 1; j < n; j++) {\n            if (isConnected[i][j] === 1) {\n                const root1 = uf.find(i);\n                const root2 = uf.find(j);\n                uf.merge(root1, root2);\n            }\n        }\n    }\n        \n    const components = new Set();\n    for (let i = 0; i < n; i++) {\n        components.add(uf.find(i));\n    }\n        \n    return components.size;    \n};\n```\n\n**Complexity**:\n* Time Complexity : `O(n ^ 2 log(n))`\n* Space Complexity : `O(n)`\n\n<br/>\n\n**Homework**:\n*  [Count Servers that Communicate](https://leetcode.com/problems/count-servers-that-communicate/)\n*  [Satisfiability of Equality Equations](https://leetcode.com/problems/satisfiability-of-equality-equations/)\n*  [Redundant Connection](https://leetcode.com/problems/redundant-connection/)\n*  [Making A Large Island](https://leetcode.com/problems/making-a-large-island/)\n*  [Smallest String With Swaps](https://leetcode.com/problems/smallest-string-with-swaps/)\n*  [Largest Component Size by Common Factor](https://leetcode.com/problems/largest-component-size-by-common-factor/)\n\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['PHP', 'Python', 'Java', 'Go', 'JavaScript']