AtCoder ABC #183 : F - Confluence

これも知ってれば典型かな…。
https://atcoder.jp/contests/abc183/tasks/abc183_f

問題

初期状態でN人がそれぞれ1人で集団を成している。
また、各人がどのクラスに属するかという情報が入力で与えられる。

以下のクエリに順次答えよ。

• 2人が指定されるので、両者が属する集団が異なるならマージする。
• 人とクラスが指定されるので、その人が属する集団にいるそのクラスの人数を答える。

解法

UnionFindで集団のマージの有無を判定し、クラス毎の人数の情報についてはmapをいわゆるマージテクで合わせて行けばよい。

int N,Q;
int C[202020];
map<int,int> M[202020];
int P[202020];

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<202020> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>C[i+1];
		M[i+1][C[i+1]]=1;
		P[i+1]=i+1;
	}
	while(Q--) {
		cin>>i>>x>>y;
		if(i==1) {
			x=uf[x];
			y=uf[y];
			if(x!=y) {
				uf(x,y);
				i=uf[x];
				j=x+y-i;
				
				if(M[i].size()<M[j].size()) swap(M[i],M[j]);
				FORR(m,M[j]) M[i][m.first]+=m.second;
			}
		}
		else {
			x=uf[x];
			cout<<M[x][y]<<endl;
		}
	}
}

まとめ

まぁこのあとCodeforcesもあるしね。