kmjp's blog

競技プログラミング参加記です

LeetCode Weekly Contest 113 : 952. Largest Component Size by Common Factor

これは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;
    }
};

まとめ

これ他サイトだと難易度どれぐらいだろうな。