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; }