import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { List<Integer> list = new ArrayList<>(); int primeNum = 0; int[] fa; int[] rank; int[] map ; public static void main(String[] args) { Solution solution = new Solution(); int cnt = solution.largestComponentSize(new int[]{ 12377,95569,53366,10979,43909,40213,22501,359,96269,82847,85829,81154,43423,2801,97049,30053,72049,84779,17659,34033,49663,10159,61283,91771,22153,93991,8779,10357,89213,2791,55465,21061,9017,44777,77876,67343,64661,28631,20107,23557,10201,86737,4534,31481,83761,8977,59743,3659,4479,42577,2011,94063,59233,69777,31957,4909,82633,70709,72977,52973,74216,93109,37328,5591,77323,91857,36259,42743,76739,94697,88339,14801,39982,59473,26153,75689,55201,12293,14669,94819,36545,33403,16183,809,12451,20602,52354,54476,51421,53267,25589,45869,13829,90821,37547,52951,80943,33329,48989,11483,21548,75323,32987,51503,16987,89911,54589,74821,25763,34283,23977,46589,87023,36979,40057,43159,12763,29339,41521,85823,57029,69259,18119,27947,97561,54669,63377,69739,72367,27793,57373,79757,30187,83,83089,47527,69899,43786,26951,84278,36721,58207,81773,60283,79641,29483,87797,76313,30236,54359,16007,99371,44501,42649,14673,95789,31907,66049,93745,93985,4591,12813,5813,89767,41045,3607 }); System.out.println(cnt); } public int largestComponentSize(int[] nums) { pre(); int cnt1 = 0; for (int num : nums) { int tmp = num; if( num == 1){ cnt1=1; continue; } List<Integer> primes = new ArrayList<>(); for (int i = 0; i < primeNum && list.get(i) <= tmp && map[tmp] == -1; i++) { int p = list.get(i); boolean find = false; while (tmp % p == 0) { tmp = tmp / p; find = true; } if (find) { primes.add(i); } } int set0 = map[tmp]>-1?map[tmp]:primes.get(0); rank[find(set0)]++; for (int j = 0; j < primes.size(); j++) { int set = primes.get(j); merge(set0, set); } } int max = 0; for (int i = 0; i < list.size(); i++) { int p = find(i); if (rank[p] > max) { max = rank[p]; } } return Math.max(max,1); } public void merge(int set0, int set1) { int p1 = find(set0); int p2 = find(set1); if (p1 == p2) { return; } if (rank[p1] > rank[p2]) { fa[p2] = p1; rank[p1] += rank[p2]; } else { fa[p1] = p2; rank[p2] += rank[p1]; } } public int find(int set0) { int tmp = set0; while (fa[tmp] != tmp) { tmp = fa[tmp]; } int root = tmp; while(fa[set0] != set0){ int p = fa[set0]; fa[set0] = root; set0 = p; } return root; } public void pre() { primeNum = 0; Arrays.fill(isprime,true); for (int i = 2; i <= 100000; i++) { if (isprime[i]) { primeNum++; list.add(i); } for(int j=i;j<=1_000_00;j+=i){ isprime[j] = false; } isprime[i] = true; } // System.out.println(primeNum); fa = new int[primeNum]; rank = new int[primeNum]; for (int i = 0; i < primeNum; i++) { fa[i] = i; rank[i] = 0; } map = new int[100001]; Arrays.fill(map,-1); for(int i = 0;i<list.size();i++){ map[list.get(i)] = i; } } boolean[] isprime = new boolean[100001]; }
原文地址:http://www.cnblogs.com/fishcanfly/p/16852747.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性