Intuitive Disjoint Set Union Find in [Java/Python3]
Java\n\nclass Solution {\n    public int findCircleNum(int[][] M) {\n        DSU dsu = new DSU(M.length);\n        for (int i = 0; i < M.length; ++i) {\n       
### Java\n```\nclass Solution {\n    public int findCircleNum(int[][] M) {\n        DSU dsu = new DSU(M.length);\n        for (int i = 0; i < M.length; ++i) {\n            for (int j = i; j < M[i].length; ++j)\n                if (M[i][j] == 1) dsu.union(i, j);\n        }\n        return dsu.getNumFrdCir();\n    }\n}\n\nclass DSU {\n    private int[] par = null, rnk = null;\n    private int numFrdCir = 0;\n\n    public DSU(int len) {\n        this.numFrdCir = len;\n        this.par = new int[len];\n        this.rnk = new int[len];\n        for (int i = 0; i < len; ++i)\n\t\t\tthis.par[i] = i;\n    }\n\n    public int find(int x) {\n        if (this.par[x] != x)\n\t\t\tthis.par[x] = this.find(this.par[x]);\n        return this.par[x];\n    }\n\n    public void union(int x, int y) {\n        int xr = this.find(x),\n            yr = this.find(y);\n        if (xr == yr)\n\t\t\treturn;\n        else if (this.rnk[xr] < this.rnk[yr])\n\t\t\tthis.par[xr] = yr;\n        else if (this.rnk[xr] > this.rnk[yr])\n\t\t\tthis.par[yr] = xr;\n        else {\n            this.par[yr] = xr;\n            this.rnk[xr]++;\n        }\n        this.numFrdCir--;\n    }\n    \n    public int getNumFrdCir() {\n        return this.numFrdCir;\n    }\n}\n```\n\nResults on Y2020M01D13Mon:\n```\nRuntime: 1 ms, faster than 100.00% of Java online submissions for Friend Circles.\nMemory Usage: 45 MB, less than 44.00% of Java online submissions for Friend Circles.\n```\n---\n### Python3\n```\nclass Solution:\n    def findCircleNum(self, M: List[List[int]]) -> int:\n        dsu = DSU(len(M))\n        for i, r in enumerate(M):\n            for j, v in enumerate(r):\n                if j > i - 1: break\n                if v == 1:\n                    dsu.union(i, j)\n        return dsu.numFrdCir\n    \nclass DSU:\n    def __init__(self, num):\n        self.numFrdCir = num\n        self.par = list(range(num))\n        self.rnk = [0] * num\n        \n    def find(self, x):\n        if self.par[x] != x:\n            self.par[x] = self.find(self.par[x])\n        return self.par[x]\n    \n    def union(self, x, y):\n        xr, yr = self.find(x), self.find(y)\n        if xr == yr:\n\t\t\treturn\n        elif self.rnk[xr] < self.rnk[yr]:\n            self.par[xr] = yr\n        elif self.rnk[xr] > self.rnk[yr]:\n            self.par[yr] = xr\n        else:\n            self.par[yr] = xr\n            self.rnk[xr] += 1\n        self.numFrdCir -= 1\n```\nResults on Y2020M01D13Mon:\n```\nRuntime: 192 ms, faster than 90.01% of Python3 online submissions for Friend Circles.\nMemory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Friend Circles.\n```\n---\n### Analysis\nTime Complexity: O(N\u03B1(N))\u2248O(N), where N is the number of vertices (and also the number of edges) in the graph, and \u03B1 is the Inverse-Ackermann function.\nSpace Complexity: O(N). The current construction of the graph (embedded in our dsu structure) has at most N nodes.\n\nSince the matrix is symmetric with respect to the diagonal, we only need to iterate through either the left-bottom or the top-right triangle. For example, in this code, this can be done by ```j``` starting from ```i``` to ```M[i].length``` instead of ```0``` to ```M[i].length```  in ```Java```, or break the iteration ```for j, v in enumerate(r):``` when ```j > i - 1``` in ```Python3```.\n\n---\n\n### References\n\nIntuitive Explanation Video\nhttps://youtu.be/0jNmHPfA_yE\n\nhttps://leetcode.com/problems/redundant-connection/solution/\nhttps://leetcode.com/problems/friend-circles/discuss/247455/easy-to-understand-union-find-disjoint-set-union-in-java-following-q684s-solution-structure\nhttps://leetcode.com/problems/friend-circles/discuss/101336/Java-solution-Union-Find\n
['Union Find', 'Python', 'Java', 'Python3']