Python 1112 ms beats 100%, Union-Find and Prime factor decomposition with Optimization
Using the input of first example,We can firstly do Prime factor decomposition for each number in A, then we can get the map:{2: [4, 6], 3: [6, 15], 5: [15, 35],
Using the input of first example,We can firstly do Prime factor decomposition for each number in A, then we can get the map:```{2: [4, 6], 3: [6, 15], 5: [15, 35], 7: [35]})```, in which values are all multiples of the key(```must be prime```). Then we can regard the first multiple as the root of all the multiples, connect each multiple with the root. In this example, we connect 6 with 4(```root```), connect 15 with 6(```root```), connect 35 with 15(```root```), because there is only one multiple in ```7: [35]```, so no connection. At the end, we can get the largest size 4, which is the result. The root of all the numbers in A is the number ```4```.\n```\nclass UnionFind(object):\n    def uf(self, n):  \n        self.uf = [i for i in range(n)]\n        self.size = [1] * n\n        \n    def find(self, x):  \n        while x != self.uf[x]:\n            self.uf[x] = self.uf[self.uf[x]]\n            x = self.uf[x]\n        return self.uf[x]\n\n    def union(self, x, y):  \n        x_root = self.find(x)\n        y_root = self.find(y)\n        if x_root == y_root:\n            return\n        self.uf[x_root] = y_root\n        self.size[y_root] += self.size[x_root]\n        self.size[x_root] = 0\n\n\nclass Solution(object):\n    def largestComponentSize(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        def primeFactors(n):  # Prime factor decomposition\n            out = set()\n            while n % 2 == 0: \n                out.add(2)\n                n //= 2\n            for i in range(3, int(math.sqrt(n))+1, 2): \n                while n % i== 0: \n                    out.add(i) \n                    n //= i \n            if n > 2: \n                out.add(n)\n            return out\n        \n        idx_lookup = {A[i]: i for i in range(len(A))} # in order to find idx in uf\n        uf = UnionFind()\n        uf.uf(len(A))\n        primeAndItsMultiples = collections.defaultdict(list) # {2: [4, 6], 3: [6, 15], 5: [15, 35], 7: [35]})\n        \n        for i in A:\n            factors = primeFactors(i)\n            for f in factors:\n                primeAndItsMultiples[f].append(i)\n\n        # we don\'t need to connect all the multiples of a prime, \n        # just use the first multiple as their root\n        for idx, multiples in primeAndItsMultiples.items():\n            if multiples:\n                root = multiples[0] # use the first multiple as their root\n                for node in multiples[1:]:\n                    uf.union(idx_lookup[node], idx_lookup[root]) # connect node with root\n                    \n        return max(uf.size)\n```\n\nInspired by `yanx1` in the comment below,  `idx_lookup` and `primeAndItsMultiples` are kind of unnecessary... all we need is a dict primeToIndex that record the index of the element in A who has p as a prime factor.\n\nThis allows the runtime to be reduced to `1112 ms`\n\n\n\n```python\nclass UnionFind(object):\n    def uf(self, n):  \n        self.uf = [i for i in range(n)]\n        self.size = [1] * n\n        \n    def find(self, x):  \n        while x != self.uf[x]:\n            self.uf[x] = self.uf[self.uf[x]]\n            x = self.uf[x]\n        return self.uf[x]\n\n    def union(self, x, y):  \n        x_root = self.find(x)\n        y_root = self.find(y)\n        if x_root == y_root:\n            return\n        self.uf[x_root] = y_root\n        self.size[y_root] += self.size[x_root]\n        self.size[x_root] = 0\n\n\nclass Solution(object):\n    def largestComponentSize(self, A):\n        """\n        :type A: List[int]\n        :rtype: int\n        """\n        def primeFactors(n):  # Prime factor decomposition\n            out = set()\n            while n % 2 == 0: \n                out.add(2)\n                n //= 2\n            for i in range(3, int(math.sqrt(n))+1, 2): \n                while n % i== 0: \n                    out.add(i) \n                    n //= i \n            if n > 2: \n                out.add(n)\n            return out\n        \n        uf = UnionFind()\n        uf.uf(len(A))\n        \n        primeToIndex = {} \n        for i,a in enumerate(A):\n            primes = primeFactors(a)\n            for p in primes:\n                if p in primeToIndex:\n                    uf.union(i, primeToIndex[p])\n                primeToIndex[p] = i\n        return max(uf.size)\n```\nYou can also check the solution [here](https://github.com/apachecn/awesome-algorithm/blob/master/docs/Leetcode_Solutions/Python/952._Largest_Component_Size_by_Common_Factor.md).
[]