これは7でもいいんでない?
https://leetcode.com/contest/weekly-contest-113/problems/largest-component-size-by-common-factor/
問題
整数をラベルに持つ無向グラフを考える。
ラベル同士のGCDが2以上となる頂点間全てに辺を張るとき、最大の連結成分のサイズを答えよ。
解法
各ラベルの値を素因数分解し、同じ素因数を持つものを順次Union-Findで連結していくだけ。
template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<20200> uf; const int prime_max = 100005; int NP,prime[100000],divp[prime_max]; vector<int> C[101010]; int pre[101010]; void cprime() { if(NP) return; for(int i=2;i<prime_max;i++) if(divp[i]==0) { prime[NP++]=i; for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i; } } class Solution { public: int largestComponentSize(vector<int>& A) { cprime(); uf.reinit(); int i,j; MINUS(pre); FOR(i,A.size()) { int x=A[i]; while(x>1) { int y=(divp[x]==0)?x:divp[x]; if(pre[y]>=0) uf(pre[y],i); pre[y]=i; x/=y; } } int ma=0; FOR(i,A.size()) ma=max(ma,uf.count(i)); return ma; } };
まとめ
これ他サイトだと難易度どれぐらいだろうな。