Union Find, java
n^2 brute force union find exceeds the time limit, uses a map here.\n```\nclass Solution {\n    public int largestComponentSize(int[] A) {\n        UF uf = new 
n^2 brute force union find exceeds the time limit, uses a map here.\n```\nclass Solution {\n    public int largestComponentSize(int[] A) {\n        UF uf = new UF(A.length);\n        \n        Map<Integer, Integer> map = new HashMap<>();        \n        for (int i = 0; i < A.length; i++)\n        {            \n            for (int j = 2; j * j <= A[i]; j++)\n            {\n                if (A[i] % j == 0)\n                {\n                    if (map.containsKey(j) && uf.find(i) != map.get(j))\n                    {\n                        uf.union(i, map.get(j));\n                    }\n                    else if (!map.containsKey(j))\n                    {\n                        map.put(j, i);\n                    }\n                    \n                    if (map.containsKey(A[i] / j) && uf.find(i) != map.get(A[i] / j))\n                    {\n                        uf.union(i, map.get(A[i] / j));\n                    }\n                    else if (!map.containsKey(A[i] / j))\n                    {\n                        map.put(A[i] / j, i);\n                    }\n                }\n            }\n            \n            if (map.containsKey(A[i]) && uf.find(i) != map.get(A[i]))\n            {\n                uf.union(i, map.get(A[i]));\n            }\n            else if (!map.containsKey(A[i]))\n            {\n                map.put(A[i], i);\n            }\n        }\n        \n        int[] counts = new int[A.length];\n        int max = 0;\n        \n        for (int i = 0; i < A.length; i++)\n        {\n            counts[uf.find(i)]++;\n            max = Math.max(max, counts[uf.find(i)]);\n        }\n        \n        return max;\n    }\n    \n    class UF\n    {\n        int[] roots;\n        \n        public UF(int length)\n        {\n            roots = new int[length];\n            \n            for (int i = 0; i < roots.length; i++)\n            {\n                roots[i] = i;\n            }       \n        }\n        \n        public void union(int i, int j)\n        {   \n            roots[find(i)] = roots[find(j)];\n        }\n        \n        public int find(int i)\n        {\n            if (roots[i] != i)\n            {\n                roots[i] = find(roots[i]);\n            }\n            \n            return roots[i];\n        }\n    }\n}
[]