[Java] 2 simple solutions one using DFS and another using union-find
Here I have given 2 solutions one using dfs and another using union-find. Bothe approach share the same initial preprocessing steps! The only thing that is diff
Here I have given 2 solutions one using dfs and another using union-find. Bothe approach share the same initial preprocessing steps! The only thing that is different is thet in union find we check size of every root node where as in dfs implementation we use dfs to find size of every connected component.\n\n**1. Using DFS**\n```\nclass Solution {\n    \n    ArrayList<Integer>[] graph;\n    boolean[] visited;\n    int count=0;\n    \n\tpublic int largestComponentSize(int[] A) {\n\t\t\n\t\t//Getting prime factors of every element in the array A\n        HashSet<Integer> primes[] = new HashSet[A.length];\n        for(int i=0; i<A.length; i++){\n            primes[i] = primeFact(A[i]);\n        }\n\t\t\n\t\t//Generating HashMap with every prime factor as key and list of elements\' index that has that particular number as prime factor as value\n        HashMap<Integer, ArrayList<Integer>> mapping = new HashMap<>();\n        for(int i=0; i<primes.length; i++){\n            for(int fact: primes[i]){\n                if(!mapping.containsKey(fact))\n                    mapping.put(fact, new ArrayList<Integer>());\n                mapping.get(fact).add(i);\n            }\n        }\n\t\t\n        //Initializing graph\n        graph = new ArrayList[A.length];\n        visited = new boolean[A.length];\n        for(int i=0; i<A.length; i++)\n            graph[i]=new ArrayList<>();\n        \n\t\t//Adding edges between nodes that share common prime factors\n\t\t//There will be duplicate node in this adjacency list. We can use HashSet but overhead is big! \n\t\t//As during dfs we do use visited array so every node is visited once so duplicate entries don\'t bother that much\n        for(ArrayList<Integer> arr:mapping.values()){\n            for(int i=1; i<arr.size(); i++){\n                graph[arr.get(i-1)].add(arr.get(i));\n                graph[arr.get(i)].add(arr.get(i-1));\n            }\n        }\n        \n\t\t//finding the size of largest connected component\n        int max = 0;\n        for(int i=0; i<A.length; i++){\n            if(!visited[i]){\n                count=0;\n                dfs(i);\n                max = Math.max(max, count);\n            }\n        }\n        \n        return max;\n    }\n    \n    private void dfs(int node){\n        visited[node]=true;\n        count++;\n        for(int nbr:graph[node]){\n            if(!visited[nbr]){\n                dfs(nbr);\n            }\n        }\n    }\n    \n    private HashSet<Integer> primeFact(int n){\n        HashSet<Integer> ans = new HashSet<>();\n        if(n==1)\n            return ans;\n        \n        while(n%2==0){\n            ans.add(2);\n            n/=2;\n        }\n        for(int i=3; i<=Math.sqrt(n); i+=2){\n            // System.out.println(n%i);\n            while(n%i==0){\n                n/=i;\n                ans.add(i);\n            }\n        }\n        if(n>2)\n            ans.add(n);\n        return ans;\n    }\n}\n```\n\n**2. Using Union Find(More effiecient)**\n\n```\nclass Solution {\n    \n    int[] sz, id;\n    \n    public int largestComponentSize(int[] A) {\n\t\n\t\t//Getting prime factors of every element in the array A\n        HashSet<Integer> primes[] = new HashSet[A.length];\n        for(int i=0; i<A.length; i++){\n            primes[i] = primeFact(A[i]);\n        }\n\t\t\n\t\t//Generating HashMap with every prime factor as key and list of elements\' index that has that particular number as prime factor as value\n        HashMap<Integer, ArrayList<Integer>> mapping = new HashMap<>();\n        for(int i=0; i<primes.length; i++){\n            for(int fact: primes[i]){\n                if(!mapping.containsKey(fact))\n                    mapping.put(fact, new ArrayList<Integer>());\n                mapping.get(fact).add(i);\n            }\n        }\n        \n\t\t//Initializing arrays for union-find \n        this.sz = new int[A.length];\n        this.id = new int[A.length];\n        \n        for(int i=0; i<id.length; i++){\n            sz[i]=1; //Initial size of each componenet is 1\n            id[i]=i; //Initially every node is root node \n        }\n        \n\t\t//Calling union with elements that share same prime factore\n        for(ArrayList<Integer> arr:mapping.values())\n            for(int i=1; i<arr.size(); i++)\n                union(arr.get(i-1), arr.get(i));\n        \n\t\t//finding the size of largest component size in disjoint set\n        int max = 0;\n        for(int i=0; i<A.length; i++){\n            max = Math.max(max, this.sz[find(i)]);\n        }\n        \n        return max;\n    }\n    \n    private int find(int node){\n\t\t\n\t\t//Finding root node\n        int root = node;\n        while(root!=this.id[root]){\n            root = this.id[root];\n        }\n        \n\t\t//Path Compression\n\t\twhile(node!=root){\n            int tmp = this.id[node];\n            this.id[node] = root;\n            node = tmp;\n        }\n        return root;\n    }\n    \n    private void union(int i, int j){\n        int root1 = find(i);\n        int root2 = find(j);\n        \n        if(root1==root2)\n            return;\n        \n\t\t//Merging smaller component into larger one\n        if(this.sz[root1]<=this.sz[root2]){\n            this.sz[root2]+=this.sz[root1];\n            this.id[root1]=root2;\n        }else{\n            this.sz[root1]+=this.sz[root2];\n            this.id[root2]=root1;\n        }\n    }\n    \n    private HashSet<Integer> primeFact(int n){\n        HashSet<Integer> ans = new HashSet<>();\n        if(n==1){\n            return ans;\n        }\n\t\t\n        while(n%2==0){\n            ans.add(2);\n            n/=2;\n        }\n        for(int i=3; i<=Math.sqrt(n); i+=2){\n            while(n%i==0){\n                n/=i;\n                ans.add(i);\n            }\n        }\n        if(n>2)\n            ans.add(n);\n        return ans;\n    }\n}\n```\n\nHere time complexity of both approach is more or less same. In both approach first thing that is different that in dfs one we create graph by adding edges and in the later one we call union function and create components with that. We know that union method\'s amortized time complexity effectively becomes small constant with path compression. \n\nNow main difference is in the last part where we find the size of the largest component! In the dfs approach we call the dfs in loop and keep track of size of each component. This approach is little ineffecient as there are duplicate nodes in the adjacency list but it doesn\'t affect that much due to the use of visited array but we do run a loop for every nbr in the adj list. Where as in the union find we find size of the root for every node so find has amortized complexity of contant and we do that also n times so this may be little bit more efficient in some cases but it doen\'t make that much difference.
['Depth-First Search', 'Union Find']