UVa-11503 : Virtual Friends

問題概要

人名のペアがF(<10^5)個与えられるので、それをマージする度にそれが含まれる集合のサイズを答える問題。

解法

union findでマージするときに数も足し合わせる。stringの処理が重くならないように注意。

acceptされたコード

計算量O(F*logF*L)。

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_F = 100000;
const int MAX_L = 20;

string names[2*MAX_F];
string indexed[2*MAX_F];

int F, N;
int pars[2*MAX_F], nums[2*MAX_F];

void init_uf(int n){
	for(int i=0; i<n; i++){
		pars[i] = i;
		nums[i] = 1;
	}
}

int get_root(int x){
	return pars[x] == x ? x : (pars[x] = get_root(pars[x]));
}

int merge(int x, int y){
	int px = get_root(x), py = get_root(y);
	if(px == py){
		return nums[px];
	}
	else{
		pars[px] = py;
		return nums[py] += nums[px];
	}
}

void solve(){
	scanf("%d ", &F);
	char buf[MAX_L + 1];

	for(int i=0; i<2*F; i++){
		scanf(" %s ", buf);
		indexed[i] = names[i] = string(buf);
	}

	sort(indexed, indexed+2*F);
	N = unique(indexed, indexed+2*F) - indexed;

	init_uf(N);
	for(int i=0; i<F; i++){
		printf("%d\n", merge( lower_bound(indexed, indexed+N, names[2*i+0]) - indexed,
				               lower_bound(indexed, indexed+N, names[2*i+1]) - indexed) );
	}
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		solve();
	}

	return 0;
}